Round 1:
1. There are n petrol bunks arranged in circle. Each bunk is separated from the rest by a certain distance. You choose some mode of travel which needs 1litre of petrol to cover 1km distance. You can't infinitely draw any amount of petrol from each bunk as each bunk has some limited petrol only. But you know that the sum of litres of petrol in all the bunks is equal to the distance to be covered.
ie let P1, P2, ... Pn be n bunks arranged circularly. d1 is distance between p1 and p2, d2 is distance between p2 and p3. dn is distance between pn and p1.Now find out the bunk from where the travel can be started such that your mode of travel never runs out of fuel.
2. There are 25 horses among which you need to find out the fastest 3 horses. You can conduct race among at most 5 to find out their relative speed. At no point you can find out the actual speed of the horse in a race. Find out how many races are required to get the top 3 horses.
3. Remove a node from a doubly linked list.
4. Implement char* itoa(int) function.
Round 2:
1. Merging 2 binary trees. (I said O(n log n log n) and he was satisfied)
2. A tree is represented in a matrix form such that A[i,j] = 1 if j is the ancestor of i. Otherwise A[i,j] = 0. Given this construct a normal binary search tree.
3. A 2D array is such that each row in it is in ascending order and each column is in ascending order. How will you search for an element in this array? (O(n) is enough)
Round 3 (Design Round)
1. A city is represented as a grid where each line represents a road. As it is a grid, all the horizontal roads intersect with all vertical roads. A bus may enter the city in the left-bottom junction with a North seeing face (direction of the bus). You can move to any of the intersections with a proper control string. Eg "LLMMR" L, R, M representes that the bus has to be turned to its left, right and then has to move one step forward and reach the next intersection. How will you design this scenario? What classes are needed? What member variables and functions are needed?
2. How will you design google map?
3. Java has an inbuilt hashmap class. It usually takes object id as a reference to hash the key values. Instead how could you make it take the state of the object (if both the objects have same set of values for all the member variables, they are in the same state) to hash the key?
hashmap.hash(new foo(), "xyz");
hashmap.hash(new foo(), "xyz");
Both of them should hash into the same. How will you do that?
Round 4
1. Given 2 billion numbers and 2 MB RAM, how will you sort the numbers? (He wanted me to discuss the external sort)
2. How will you find the first k smallest elements in a given unsorted array in O(n) at the worst case?
3. Given a sorted array A, how will you find out elements in that array (a,b,c) such that the sum of the squares of a and b is the square of c? You need to do it in O(n^2)
1. There are n petrol bunks arranged in circle. Each bunk is separated from the rest by a certain distance. You choose some mode of travel which needs 1litre of petrol to cover 1km distance. You can't infinitely draw any amount of petrol from each bunk as each bunk has some limited petrol only. But you know that the sum of litres of petrol in all the bunks is equal to the distance to be covered.
ie let P1, P2, ... Pn be n bunks arranged circularly. d1 is distance between p1 and p2, d2 is distance between p2 and p3. dn is distance between pn and p1.Now find out the bunk from where the travel can be started such that your mode of travel never runs out of fuel.
2. There are 25 horses among which you need to find out the fastest 3 horses. You can conduct race among at most 5 to find out their relative speed. At no point you can find out the actual speed of the horse in a race. Find out how many races are required to get the top 3 horses.
3. Remove a node from a doubly linked list.
4. Implement char* itoa(int) function.
Round 2:
1. Merging 2 binary trees. (I said O(n log n log n) and he was satisfied)
2. A tree is represented in a matrix form such that A[i,j] = 1 if j is the ancestor of i. Otherwise A[i,j] = 0. Given this construct a normal binary search tree.
3. A 2D array is such that each row in it is in ascending order and each column is in ascending order. How will you search for an element in this array? (O(n) is enough)
Round 3 (Design Round)
1. A city is represented as a grid where each line represents a road. As it is a grid, all the horizontal roads intersect with all vertical roads. A bus may enter the city in the left-bottom junction with a North seeing face (direction of the bus). You can move to any of the intersections with a proper control string. Eg "LLMMR" L, R, M representes that the bus has to be turned to its left, right and then has to move one step forward and reach the next intersection. How will you design this scenario? What classes are needed? What member variables and functions are needed?
2. How will you design google map?
3. Java has an inbuilt hashmap class. It usually takes object id as a reference to hash the key values. Instead how could you make it take the state of the object (if both the objects have same set of values for all the member variables, they are in the same state) to hash the key?
hashmap.hash(new foo(), "xyz");
hashmap.hash(new foo(), "xyz");
Both of them should hash into the same. How will you do that?
Round 4
1. Given 2 billion numbers and 2 MB RAM, how will you sort the numbers? (He wanted me to discuss the external sort)
2. How will you find the first k smallest elements in a given unsorted array in O(n) at the worst case?
3. Given a sorted array A, how will you find out elements in that array (a,b,c) such that the sum of the squares of a and b is the square of c? You need to do it in O(n^2)
No comments:
Post a Comment