Akamai Interview Question Java Developers
Country: United States
why a min heap if you want max elements and why is the size 1000 if only 100 elements are needed
You can use an array and a heap at the same time! Use the array implementation of the heap.
Let's say it is not 100 , it is 5 .
And my current heap is { 27,13,5,10,8}
and new number that comes is 9. How do you find , eliminate 5 and restructure the heap. ??
Won't it be good to just keep circular list/queue, so that i know the range [ min, max] of my current top 100 elements. if number scanned is out of that range, we ignore and if number is in that range we insert it in it's correct place.
simply store initial 100 elements in sorted order then if next number is greater then 100th number then simply delete 100 th number and add tht element(at appropriate position) .. keep doing till last .. :)
yeah but in implementing the same we can maintain a heap to know the largest value in the current list of 100 numbers.
Wait, you will have to sort the incoming stream until you get the first 100 numbers. Then if the next number is greater than any of the prev, you have to push down the set by 1, so in this worst case, you will have to do this about 100 times N. Wouldn't a binary heap will allow the insert option in big-O log base 2 of 100 times N? So be faster.
randomly select k elements as an observe sample set. K should be neither too large nor too small.
observe k. Since the element is integer. select a digit number as threshold to reduce the list size. let's say, after observing, we pick 5 as digit number. then we scan the whole list, and just load the element which is equal or larger than 10000 in to memory.
redix sort picked elements in memory.
return top 100
average complexity should be n. It does not work in some special cases.
instead of sorted array, use a heap.
- Anonymous May 21, 2013