Archive for the ‘Algorithms’ Category

Q: You are given an array of integers. For each element x find a suitable y such that
1. Val(Y) < Val(x)
2. Position(Y) < Position(X)
3. Position of Y should be maximum as possible
4. If there is no such Y, set it to null

Try to achieve complexity better than O(n^2).

A: Use a doubly linked list with following insertion and maintenance rules –
1. Linked starts with null and at any point, parent node is the value of Y for operational element. The prints of Y happens at the time of element insertion.
2. For each element X, Start with the tail of the linked list.
> If its null node, add a node X as its successor.
> If linked list node element is less than X, add a new node as its successor.
> If node element is greater equals X, delete that node(including its tail) and re-do comparison with its parent.

Sample run
Say for array 7, 1, 4, 8, 5, 6, 2

Operational Element Linked List Operation taken Printed Result (X, Y)
7 null -> 7 Added node 7 7, Null
1 null -> 1 Deleted node 7 and added node 1 1, Null
4 null -> 1 -> 4 Added node 4 4,1
8 null -> 1 -> 4 -> 8 Added node 8 8,4
5 null -> 1 -> 4 -> 5 Deleted 8 and added 5 5,4
6 null -> 1 -> 4 -> 5 -> 6 Added Node 6 6,5
2 null -> 1 -> 2 Deleted 6, then 5, then 4 while traversal from tail and added 2 2,1

 

PS: We do complete traversal of linked list from right to left. We can have a step further by maintaining the linked list in such a manner, that we can do binary search on it (by storing position index separately). It can be more optimized by using binary search as linked list is always sorted.

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 number n, find a set such that –

  • Sum of all the elements should result into n.
  • Multiplication of all the elements should be greater than any other similar set (whose elements result n when summed up).

A. This is a very interesting problem as we have to go through every combination and calculate and compare the multiplication. Since, there is no restriction on the length of the subset, it makes problem much more interesting.

I propose use of dynamic programming here. We will start computing the f(n) from 1

At every stage, we have to compute all combinations of f(1).. f(n-1)

f(n) = max {

f(1) * f(n-1)

f(2) * f(n-2)

….. }

 

To avoid repeated operations, we can store start computing f(1).. f(n-1)  one by one and do the book keeping of the result.

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. There are n nuts and corresponding bolts. However, all nuts and bolts are shuffled and we have to device a technique to pair them.

  • No two pairs are of same size.
  • Each nut has exactly one bolt for it.
  • You can’t compare nut with a nut and same with bolt.
  • You can determine by a comparison if a nut is greater or a bolt is greater.

A. This problem can also be solved in a quick sort kind of technique.

  • Pick up nut n1 with all bolts. Divide all bigger bolts on one side and smaller bolt on other side. One bolt say b1 matches n1 to make the pair.
  • Take nut n2 and compare with bolt b1. If bigger bolt is required look in greater set otherwise in the smaller set.
  • Do the same with rest of the nuts. This way we are saving the number of comparisons by categorizing.

Time complexity is approximately O(nlogn)

Sort a Binary Array

Posted: February 13, 2011 in Algorithms, data structures

Q. Given a binary array of 0 and 1, you have to sort it such that all 0s lie on left side followed by all 1. The sorting should not use any external data structure.

A. The best approach is to use a quick sort kind of algorithm. Here, its only 0s and 1s hence, sorting will happen in O(n) time as we don’t need to call it recursively.

  • Maintain two pointers left and right.
  • Start traversing left pointer towards right until 1 is encountered.
  • Start right pointer towards left until 0 is encountered.
  • Swap elements at both pointers.
  • Continue doing so until left and right pointer converge.

Since, we have to traverse the array only once, sorting happened in O(n) time.

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