Author |
Topic: Microsoft Interview (Read 5298 times) |
|
Bassem
Newbie
 
Gender: 
Posts: 1
|
 |
Microsoft Interview
« on: Dec 9th, 2005, 11:42am » |
 Quote  Modify
|
Hi
These are some of the questions I got today in a MS interview.
1. Delete a node from a linked list given its index.
2. Write a function that takes a string of signed hex digits and returns the equivilant integer. similar to atoi but takes hex numbers instead, e.g. given "FF" it should retun 255 and so on. It should also return -1 in case it is given an invalid string like "1AZ".
3. Write code to rotate words in a string, e.g. "This is a test" --> "test This is a". it should take a string and number of rotations to do.
4. Complexity of binary trea search, hash table search.
5. Binary Tree implementation without pointers.
|
|
 IP Logged |
|
|
|
Vincent
Guest
|
1. This is an elementary operation on linked list... Google it if you really want the answer 
2. What should the function return for the string "-1"? Returning -1 for an error when -1 may be a valid value is a little odd to me...
3. Interesting... These strings operations can be easily confusing. Find the nth space from the end, cut and inverse? With std::string this would be easy
4. Complexity? In best, average, worst case?
Binary Tree: O(1), O(log(n)), O(log(n))
Hash table: O(1), O(1), O(n)
5. Use a vector where the element at index i has its left child at 2i+1 and right child at 2i+2
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Microsoft Interview
« Reply #2 on: Dec 17th, 2005, 2:29pm » |
Quote Modify
|
on Dec 17th, 2005, 1:31pm, Vincent wrote:
4. Complexity? In best, average, worst case?
Binary Tree: O(1), O(log(n)), O(log(n))
Hash table: O(1), O(1), O(n) |
|
O(log(n)) for worst case of a binary tree is onlyl if it's a balanced binary tree. Otherwise it could essentially be a linked list in the worst case. So O(n)
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
algo_wrencher
Newbie
I am not insane, I enjoy every moment of it!
Posts: 44
|
|
Re: Microsoft Interview
« Reply #3 on: Dec 23rd, 2005, 12:00pm » |
Quote Modify
|
In the rotate the words , theres a general strategy that even the older text editors use. Put each word in to a node of a linked list, now you are done! start printing by putting the no. of rotations in a loop..
|
|
IP Logged |
|
|
|
kanagavel_india
Newbie
Gender:
Posts: 7
|
 |
Re: Microsoft Interview
« Reply #4 on: Feb 1st, 2006, 1:20am » |
Quote Modify
|
Hi,
I guess the solution for rotating words in a string., But it uses the temporary buffer to store the output., Can you anybody give the solution without using extra memory ....
void rotateOneWord(char *x,int noOfRotate)
{
char *tempBuffer;
int i;
tempBuffer = (char *)malloc(strlen(x) + 1);
for(i=0;i<noOfRotate;i++)
{
sprintf(tempBuffer,"%s %s",strstr(x," ")+1,strtok(x," "));
strcpy(x,tempBuffer);
}
free(tempBuffer);
}
Yours
Kanagavel A
|
|
IP Logged |
|
|
|
algo_wrencher
Newbie
I am not insane, I enjoy every moment of it!
Posts: 44
|
|
Re: Microsoft Interview
« Reply #5 on: Feb 1st, 2006, 11:06pm » |
Quote Modify
|
I am able to recall a solution Rivest Cormen et al has suggested. When you create a node on heap, you can take its address and then create the next node in the list and XOR its address with present nodes' address. Store it in the present node. Do similar for previous node of present node. This way the node structure cud be like iI am writing a doubly linked list,to be more generic)
struct node{
void *p; //generic data element of node
long pXn;//XOR val of present and next node add
long pXpr;//XOR of present and prev node
};
Now when u traverse or do somethng else with the link list, assume you reach a node. You know its address nd hence you can agin XOR it with the pXn value stored in it to get the next address.
Hope it made some sense... 
|
|
IP Logged |
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: Microsoft Interview
« Reply #6 on: Feb 2nd, 2006, 3:20am » |
Quote Modify
|
It doesn't make sense at all. Instead of storing the Xor'ed value, you might as well store the previous and next pointer. The trick of XOR'ing the pointers was to store the previous and next pointer in the same variable. You still can move along the list by keeping the address or 2 adjacent nodes.
For the word rotation problem, I would first count the words (say w) and reduce the rotation count mod w (call it n). If n = 0, we are done, if not, find the nth space or group of spaces, cut the string there and switch the sides, adding a space in the middle.
|
|
IP Logged |
|
|
|
algo_wrencher
Newbie
I am not insane, I enjoy every moment of it!
Posts: 44
|
|
Re: Microsoft Interview
« Reply #7 on: Feb 2nd, 2006, 10:08am » |
Quote Modify
|
Oops....that was really nonsense! This shows how one can do wonders when awaken from sleep forcibly. I am sorry.
But one thing here Grimbal, I guess this technique needs a temp variable where you would be keeping the previous value to XOR with the value in the current node to get the next node. Am I recalling right this time(or else pls make me do so)??
|
|
IP Logged |
|
|
|
algo_wrencher
Newbie
I am not insane, I enjoy every moment of it!
Posts: 44
|
|
Re: Microsoft Interview
« Reply #8 on: Feb 2nd, 2006, 10:17am » |
Quote Modify
|
on Feb 2nd, 2006, 3:20am, Grimbal wrote: If n = 0, we are done, if not, find the nth space or group of spaces, cut the string there and switch the sides, adding a space in the middle.
|
|
Can you explain and clarify this with the same string given in the question above.
This is a test-----Roate by 3 clockwise--->test This is a
4%3=1
pick it from * as
This * is a test---switch sides---> is a test This ??
|
|
IP Logged |
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: Microsoft Interview
« Reply #9 on: Feb 3rd, 2006, 9:20am » |
Quote Modify
|
Oops, according to the problem, the rotation it is the other way around.
0: This is a test
1: test This is a
2: a test This is
3: is a test This
4: This is a test
5: test This is a
6: a test This is
7: is a test This
So you have to count the spaces from the end. Or count w-n from the left.
Let's take "This is a test" rotated 7 times.
There are 4 words, w=4.
To rotate 7 times is like rotating 3 times, n = 7%4 = 3.
Take the 3rd space from the end (or the (4-3)st space from the start): "This*is a test".
Cut at the star, swap "This" and "is a test" to make "is a test This".
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print
Remove