CareerCup

For part 1 of the problem, use min-heap of size k.

For part 2 of the problem,

1. get the first k number from the stream, and the smallest number of these k number, say mink

2. store the first k number into temp file

3. continue scan the stream, put the number larger than mink into memory buffer

4. if memory buffer is full (size larger than m), merge the buffer into temp file
1. only keep the top k larger number
1. get the new mink (k-th large number)

5. empty the memory buffer, go back to step 3 until the stream end

For part1 of the problem, use a min-heap of size k. After a number is read from the stream, if the size of the heap is less than k, insert it into the heap. Otherwise, if the given number is greater than the min-value of the heap, evict the min value and insert the given number into the heap. At the end, you will have top k elements left in the heap.

For part2, let L = m/k(m<k, per the question). Here again use a min-heap, but of size k/(L+1). In the first pass, find out the top k/(L+1) elements. In the second pass, find out the next top k/(L+1), by inserting into the heap only the elements which are less than the first top k/(L+1). Like this, make L+1 passes over the data, each time capturing a window of k/(L+1) ordered elements. In the end, we'll be left with top k elements.

For every m numbers from the stream, create a sorted list and write it to a file. Once you have the stream completed you would have N files each with m sorted numbers in them. This is when you would do an external merge sort on all of the files and have a final sorted list. Take the first K numbers.