Amazon Interview Question
Software Engineer / DevelopersAbove two are inefficient solutions.
if there are n numbers of which we need to find smallest first k elements, there is a solution to do this in O(n + k(log k)) if the final result should be sorted. if the final result doesn't need to be sorted then it can be done in O(n).
Refer to: http://en.wikipedia.org/wiki/Selection_algorithm
The two solutions below my post are both inefficient. Moreover, suarabhroongta2's solution is wrong and the solution using Max heap reduces to O(n log(k)).
Why not use a min heap,and carry out the min heap operation k times at any given point in time.
Assuming k << N,where N is the total no. of elements in the heap, the selection step would take approximately k*log(N)time.
I dont understand how did u get k* log(N) ...can you please explain. Like for each element from N elements if we insert into heap ...it will take (log k) for each insertion.... wont it?...or I didnt understand your algorithm clearly
@random: When we use a min heap, we don't know when to update the heap or just leave off the incoming number from the stream.
So we need to use a max heap of size "N".
Initially construct a MAX HEAP of the first "N" input numbers from the stream
updateheap(H, num) {
if (H.GetRoot().GetValue() < num) return;
H.DecreaseKey(H.GetRoot(), num);
}
Why not store in a binary search tree and output the contents in inorder tree traversal?
There are several parts of the question.
1) How to store the entire set of data?
Since there is no much requirement stated, we can simly use list or vector and add new item at the end.
2) How to get only the n smallest item?
A max heap or Binary search tree (BST)of size n will do the job. If total number of items is much larger than n it won't be efficient to keep all the items in max heap or BST. In stead keep only n smallest item in max heap or BST and then every time you get a new item you have to replace the max item with new item if it is greater and then rebuild the heap or BST. The time complexity will be log(n) in both cases.
3) Do you need the first n smallest items in sorted order?
Heap won't keep the items sorted whereas BST will do the job.
Max heap
- Anonymous November 12, 2009