Archive for the ‘Microsoft’ Category

Get The Job

Posted: November 21, 2011 in Microsoft, Puzzles

Q. A company plan to recruit people. But, ends up finding many more than eligible people including you :). So, they plan a strategy to cut short the people to their suit the headcount of their requirement.

People will be lined up in a queue 1, 2, 3… N.  At first phase, people at odd locations will be eliminated. Same thing will apply for next phase.

For example,

Round 1: 1, 2, 3, 4, 5, 6….N

Round 2:  2, 4, 5.. N  (People at odd locations eliminated)

Round 3: 4, 6… N (People at odd locations eliminated)

 

Y0u look charming. So, you get a choice for your position. Given the value of N, where will you position yourself to take up the job ??

 

A. I would choose position is the last power of 2 within N

for example, if N=17, the last power of 2 is 16 (2^4). Why ?? Think and tell me 🙂

Save the Prisoners

Posted: February 13, 2011 in Algorithms, Microsoft, Puzzles

Q. There are 10 prisoners and jailer said he will play a game with them next morning. He will make all of them stand in a row and put either of black or white hat on their head. Since, they are standing in a row, they can see the hats in front of them but not the one their head or heads behind them.

Starting from the last, jailer will ask each prisoner what is the color of his own hat. If prisoner gives wrong answer, he will shoot him right at that moment.

Prisoners have to come up with a strategy such that maximum of them can be saved.

A.

The last prisoner will say black if there are odd number of black hats in front of him. For simplicity, lets assume they are in odd number.

  • Second last prisoner can count the black hats in front of him. If he gets odd number, he can conclude the hat on his head is white and black otherwise.
  • Third last prisoner, will keep his ear open on the previous answer and then he’ll calculate of total black hats in front of him and behind him. That way he can decide if total is a odd number and can predict his hat’s color.
  • Using this technique, n-1 prisoners can be guaranteed to be saved.

 

Q. Given a binary tree, you have to print it in zigzag order of breadth first traversal. For example

Should be printed as  {A, B, C, G, F, E, D, H, I, J, K , L, M}

A. We have to use two stacks for doing this operation

  • At every level, we will push the nodes in one stack and print them.
  • At every push, print the node.
  • At every pop, push the children in another stack.
  • When the stack is empty change the traversal direction. i.e. if its left and then right node, it will be changed as right and then left node.

For example, above stack will result in following operation

  • Push A in stack 1. A printed.
  • Pop A and push B n C in stack 2. B and C printed. Direction is left -> right.
  • Change the direction and child stack reference. Direction becomes right -> left and stack 1 becomes the new child stack.
  • Pop C, this will print and push G and C. Since direction is right, left now, G is taken up first.
  • Similar operation keeps repeating till both stacks are empty.

Q. Given a linked list, you have to detect if there is a loop in it.

  • Its not necessary that linked list is a circular one.
  • Get the node from where, the loop starts.
  • Changing the data structure of nodes is not allowed.

A. Detecting the loop –

  • Maintain two pointers for traversing the list
  • Increment the pointers in parallel but with different speeds. Say pointer one by one and pointer two by two.
  • If linked list is not in a loop, pointer B will reach the end. Otherwise, at some point, it will come as same node at which pointer A resides.
  • If both pointers come to same node, we can conclude there is a loop.

Getting the length of the loop –

  • When both pointers are at same node via above traversal, we can conclude that node resides within the loop.
  • Move only one pointer till it comes back to original node. We can use the other pointer for comparison.
  • If it takes n steps, the length of loop is n.

Finding the starting point of loop –

  • Now, we have the length of the loop.
  • Set both pointers to starting node of the linked list.
  • Move pointer B by n nodes (where n is the length of the loop).
  • If pointer A and B are at same node, we have the starting of the loop.
  • If they are at different nodes, move both by one node and keep doing it till they point to same location.
  • The convergence point will be the starting point of the linked list.

All of the above operations can be performed in O(n) time. Hence, overall time complexity is O(n).

Q. There is a bi-dimensional array. All the rows and columns of this array are sorted in ascending order. Example –

3 32 34 39
4 35 38 40
6 56 57 77
45 78 88 90

Device an algorithm which can search an element in this array within O(n) time.

A. Start from top-right.

  • If search key is lesser than current element, move towards left.
  • If search key is greater, move towards down.
  • Keep doing the same thing until you reach the element.
  • If you reach first column/last row and couldn’t move further, we can conclude the search key is not present in the array.

In worst case, search key will be bottom-left element and will need 2n comparisons. Hence, overall complexity is O(n).