I faced this company during campus placements.
There was a preliminary test(usually online) followed by another online coding round and then followed by two personal interviews.
I hardly rememeber any questions from the first two rounds. Following are some of the questions that I remember from the two personal interviews:
Q1. You are given 'n' nuts and 'n' bolts. Each nut will fit to exactly one bolt and viceversa. For a given nut and a bolt, you can check if the nut is large for the bolt or the nut is small for the bolt or they form a perfect fit. There is no way you can compare two nuts or two bolts. Given this scenario, design an algorithm to identify the perfect fit pairs.
A. The idea is something similar to quicksort. Randomly pick a bolt and compare it with every other nut. Place all the nuts which are larger for the bolt in one set and all the nuts which are smaller in other set. Now, pick the nut which is a perfect fit for the bolt and make the split over the other bolts is the same way as described above. Repeat the operation on thw two sets recursively(Divide and conquer).
Q2. What are heaps? Where are they used and what are the running times for each of the operations performed on a heap.
Please note that the running time complexity of Build-Heap operation is O(n) and make sure that you know the proof for it.
Q3. How are the databases implemented? What data structure is used?
A. B-Trees. Important to know about B-Trees.
These are the questions that I remember.
No comments:
Post a Comment