Woodstock Blog

a tech blog for general algorithmic interview questions

[CC150v4] 20.6 Top Million From Billion


Describe an algorithm to find the largest 1 million numbers in 1 billion numbers.

Assume that the computer memory can hold all one billion numbers.


There’re enough discussion on Top K problems so far in this blog. The suggest solutions is:

  1. Sort

  2. Min Heap, O(n logm) time.

  3. Quickselect algorithm. O(n) time.