Archive for the ‘inMobi’ Category

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)

Advertisements

Q. You are given 9 balls. Out of these, 8 are of 1kg and 1 is heavier by 0.5 kg. Given a weight balance which can take tell you which side is heavier at a given trial, you have to compute heavier ball by weighing only twice.

A. Divide 9 balls in groups of 3.

  • Compute the heavier group using balance by keeping two groups on it. If they come as equal, we can conclude third group contains the heavier ball.
  • After we have the group that contains the heavier ball, keep the two balls on the balance, you will get the heavier one. (In case, both are equally weighed, the left out will be the heavier one)

 

Retrieval From Stack

Posted: February 12, 2011 in Algorithms, Amazon, data structures, inMobi

Q. From a given stream of numbers, I should be able to retrieve latest element. Also, you have to support reading the minimum of elements encountered so far.

A. For storing and retrieving the elements, stack is the best data structure enforcing LIFO traversal. For keeping the minimum value, we need to implement another stack in parallel.

  • The minimum element stack will keep the minimum element only for a particular node.
  • If new element, is lesser than current minimum, push the new number in the minimum stack.
  • If new element is greater than current minimum, push the old minimum again in the minimum stack.
  • While popping out any element from the main stack, pop out the respective node from the minimum stack as well.

Reading the minimum value will hence be a operation of complexity O(1).

Maximum Subset Sum Problem

Posted: February 12, 2011 in Algorithms, Amazon, inMobi, Puzzles

Q. There is an array of n integers which contains positive as well as negative values. You have to write an algorithm to find a subset whose sum is maximum.

A1. Use divide n conquer. Divide the problem into two, compare best case of left, right and maximum subset at the junction.

For checking the maximum subset at the junction, we have to get maximum subset at the corners and merge them. The complexity of this approach will be nlogn.

A2. First, you can convert the list into a list of cumulative sums, turning [5,-2,10,-4] into [0,5,3,13,9]. Then walk through the list of cumulative sums, to get the maximum positive difference. If minimum lies before the maximum in the cumulative sum, then that is the answer. For example, minimum here is 0 and maximum is 13. The answers will be numbers contributing towards it [5,-2, 10]

The gist of the concept is to get the maximum positive delta.