Question

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.

Solution

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.