## Interview Question

## Interview Answer

6 Answers

Use a sorted generic list. If the number of elements is < 100 Add the incoming number to the list. else if the incoming number is greater than the zero element of the list Add the incoming number to the list remove the zero element from the list to keep the number of elements at 100.

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).

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)." 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.

## Add Answers or Comments

To comment on this, Sign In or Sign Up.

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.