Interview Question

Software Development Engineer In Test Interview Seattle, WA

2. Find top 100 maximum number from a continuous input

  stream.
Answer

Interview Answer

6 Answers

4

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.

Interview Candidate on Dec 6, 2012
1

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.

Developer on Dec 7, 2012
0

The interview candidates solutions is the best, n insertion * log n for each heap insert - > nlogn

Developer: n * n = n^2

Hamid Dadkhah on Dec 9, 2012
0

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

Anonymous on Dec 10, 2012
0

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.

Harry on Dec 23, 2012
0

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

gman on Jun 22, 2014

Add Answers or Comments

To comment on this question, Sign In with Facebook or Sign Up