Location : Noida Sector 132, India

Referred by my friend.

Interviewers were very friendly.

Round 1 (40-50 min)
1. Discussion about projects
2. Given a m*n matrix and q queries. Queries are of following format :
a b c d
where a and b are top left coordinates
c and d are bottom right coordinates.
For each query, find sum of elements in the rectangle bounded by top left coordinates (a,b) and bottom right coordinates (c,d)
3. A factory contains 10 machines that produces balls. All machines produce balls of some particular weight e.g. 100 g. But one of the machine is defective and is producing balls of 90g. You are given a weighing machine. You can use it to weigh as many balls as much you like. How many minimum weighings are required to find the defective machine.

Round 2 (40 - 50 min)
1. Discussion about projects.
2. Given a N-bit binary number, find the next largest binary number with same number of set bits in original number.
For ex : 101 ---> 110
3. Given an array of 2*n numbers a1,a2,....an,b1,b2,....bn. Arrange the elements of array as :
a1,b1,a2,b2,a3,b3,.....an,bn.
(Without using extra space)
4. What is constructor ? What is destructor?
Follow up : How to keep track of live objects of a class without using global variables.
5. Given an array a1,a2,......an and an index 1 <= i <= n. Reverse the array around that index.
For ex : a1, a2, a3, a4, a5, a6 and i = 3
Output : - a4, a5, a6 , a1 , a2 , a3
(Without using extra space)

Round 3 (40-50 min)
1. Discussion about projects.
2. Given a binary search tree, multiply all elements by -1. Now arrange the elements such that it will again form a binary search tree.
3. Asked me to write all sorting algorithms name and their time complexities.
Follow up : Given N sorted elements and M elements are being added to it ( M <<<< N), which sorting algorithm would you prefer and why?

Round 4 (40 - 50 min)
1. Discussion about projects
2. Given a binary tree. Remove all nodes whose subtree has sum less than K.
3. There are n hills on a mountain. i th hill contain ai gems. You can collect all gems from a hill but you cannot collect gems from adjacent hills. Find the maximum number of gems you can collect.
4. 100 ants are sprinkled on a rod. Ants can move at the speed of 1 m/s. Ants have a peculiar property, they reverse their direction on collision. Find the total time after which all ants will fall from the rod.

Round 5 [10-15 min]
Write a mathematical expression to find the average of 4 integer numbers. Avoid integer overflow. Only integer part of average is required.
For ex : 3,3,4,3 ===> 3