wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> cs >> Microsoft Interview
        
(Message started by: Bassem on Dec 9^th, 2005, 11:42am)

Title: Microsoft Interview
Post by Bassem on Dec 9^th, 2005, 11:42am

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.

Title: Re: Microsoft Interview
Post by Vincent on Dec 17^th, 2005, 1:31pm

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

Title: Re: Microsoft Interview
Post by towr on Dec 17^th, 2005, 2:29pm

on 12/17/05 at 13:31:36, 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)

Title: Re: Microsoft Interview
Post by algo_wrencher on Dec 23^rd, 2005, 12:00pm

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..

Title: Re: Microsoft Interview
Post by kanagavel_india on Feb 1^st, 2006, 1:20am

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

Title: Re: Microsoft Interview
Post by algo_wrencher on Feb 1^st, 2006, 11:06pm

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... ;)

Title: Re: Microsoft Interview
Post by Grimbal on Feb 2^nd, 2006, 3:20am

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.

Title: Re: Microsoft Interview
Post by algo_wrencher on Feb 2^nd, 2006, 10:08am

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:()??

Title: Re: Microsoft Interview
Post by algo_wrencher on Feb 2^nd, 2006, 10:17am

on 02/02/06 at 03:20:34, 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?????

Title: Re: Microsoft Interview
Post by Grimbal on Feb 3^rd, 2006, 9:20am

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".