Archive for the ‘data structures’ Category

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

Q. There are k sorted lists and we have to merge them to make a single sorted list in best time.

A. I used min heap of size k to contain one element of each list. Each node of heap also contains the id of the list it belongs to.

  • Pick out first element of each list and push it into heap.
  • Take the minimum element out of the heap. Record the list it belongs to say list j.
  • Push the next element from list j back into heap.
  • Repeat the operation till all elements are parsed.

If all lists are of length n, each element has to pushed into heap at some point.

Complexity for pushing the element is logk in heap.

Overall complexity will be O(nk logk).

Q. You have an array of integers. Device an algorithm that can return all possible pythagorean triplets within them.

Example, (a,b,c) is a valid answer if    ”  a sq  + b sq  = c sq ”

A. My answer takes O(n sq) time.

  • Square all elements and keep them in an array. Time taken – O(n).
  • Our problem is simplified get numbers (a,b,c) such that to a + b = c.
  • Sort the array. Time taken O(nlogn)
  • Keep a as first element and c as last element. Try to find last b where a+b <=c
  • Store the index of that last b. Because a+b will be > c for further elements.
  • Now, search for the sum a+b within [b+1, c]. Binary search can be used.
  • If no triplet is found, increment a to next location and repeat the process.
  • Time complexity O(n sq).

Since O(n sq) is the most dominating its the overall time taken in this process.

Interviewer was looking for a solution that takes O(nlogn) and I am still thinking about it. 🙂