Get 100 highest numbers from an infinite list
- by Sachin Shanbhag
One of my friend was asked this interview question -
"There is a constant flow of numbers coming in from some infinite list
of numbers out of which you need to maintain a datastructure as to
return the top 100 highest numbers at any given point of time. Assume all the numbers are whole numbers only."
This is simple, you need to keep a sorted list in descending order and keep a track on lowest number in that list. If new number obtained is greater than that lowest number then you have to remove that lowest number and insert the new number in sorted list as required.
Then question was extended -
"Can you make sure that the Order for insertion should be O(1)? Is it possible?"
As far as I knew, even if you add a new number to list and sort it again using any sort algorithm, it would by best be O(logn) for quicksort (I think). So my friend told it was not possible. But he was not convinced, he asked to maintain any other data structure rather than a list.
I thought of balanced Binary tree, but even there you will not get the insertion with order of 1. So the same question I have too now. Wanted to know if there is any such data structure which can do insertion in Order of 1 for above problem or it is not possible at all.
