Amazon Interview Question
Senior Software Development EngineersCountry: United States
If in memory, radix sort and print off last 50 elements. If data is larger than memory (not the case in this problem, but hey, keep a min heap for the 50 largest data items. Only insert into heap and then pop if new value is larger than heap.peak() (aka the smallest value in the heap). This ensures the heap always has the largest 50 seen so far without the overhead of having to maintain a perfect sort over the 50.
Both run in O(n) time. Radix sort is obvious, but the heap will in the worst case run O(n*lg 50)=O(n) since the size of the heap is a constant 50
I think the problem is analogous to "Find K Max elements in an unsorted array"
- starter September 26, 2014