The interview candidates solutions is the best, n insertion * log n for each heap insert - > nlogn Developer: n * n = n^2

"I think the key of the question would be 100, a fixed number. The sorting time of 100 numbers would always be O(1)." This is bad design given that if it was something other than 100, then this does not hold true. Even if it was always true, using a heap (or Priority Queue in java) will give you a better run time. Here's why: for each insertion you will sort, this will be 100*log(100) for each incmoming number, and you might have to remove a number, which will be logn (assuming you are using an array and using binary search to search the element), and finally, o(1) for each insertion... using a priority queue will give you log(100) for each removal, and log(100) for each insertion, and o(1) for a comparison with the head of the heap comparing solutions this is: 100*log(100) + log(100) + 1 V.S. log(100) + log(100) + 1, solution 2 is much better timewise, and spacewise it is the same.

Use a min heap to store the top 100 maximum numbers. If the incoming number is greater than the top element replace it and sort the heap.

There is a blog discussing a similar coding interview question at http://codercareer.blogspot.com/2011/09/no-05-least-k-numbers.html. The first solution is suitable for this problem.

I think the key of the question would be 100, a fixed number. The sorting time of 100 numbers would always be O(1).