Glassdoor Interview Question: Given a list of one million n... | Glassdoor

Interview Question

Software Engineer Interview Sausalito, CA

Given a list of one million numbers, how will you find the

  top n numbers from the list in an efficient way
Answer

Interview Answer

2 Answers

2

Use a custom brew of heapsort:
1. Create a max-heap, O(n)
2. Take off the top 10, 10*O(log(n)) = O(log(n))

O(n) + O(log(n)) = O(n)
Done in O(n) time. Cannot be done faster.

ss on Jan 28, 2012
11

previous answer isn't exact - I think he's confusing n and 10. The given question is find the top n given a list of m = 1,000,000.

correct answer is:
1. create a min heap
2. take first n of m elements and place in the heap (O(n))
3. for each (m-n) remaining elements, if it is greater than find-min of the heap, insert into heap and delete min. (worst case O((m-n)log n) if the list is sorted.

net result is you can do this in O(n) memory usage and worst-case O((m-n)logn) runtime.

ramma lamma ding dong! on Jun 1, 2013

Add Answers or Comments

To comment on this, Sign In or Sign Up.