A strong answer
Sorting needs all n items in memory and O(n log n) time; neither is acceptable for a billion items arriving as a stream. Instead, keep a min-heap of at most k items, the best k so far. Its root is the smallest of them, which is exactly the bar a new item must clear and the item to evict if it does. For each item: if the heap has fewer than k, push; else if the item beats the root, replace the root and sift down; else skip after one comparison. That is O(n log k) time and O(k) memory, and the answer is always current, so it also works for continuous streams. In Python, heapq.nlargest does this.
If all the data is in memory and k is large, quickselect finds the kth largest in O(n) expected time, and the elements on one side of it are the top k. If k is a large fraction of n, sorting is simpler and not much slower.
For data spread across machines, compute the top k on each machine with its own heap, send those k-item lists to one place, and merge them, again with a size-k heap, which keeps network traffic at k items per machine. For the k most frequent items in a huge stream, exact counting needs memory proportional to the number of distinct items; when that is too much, approximate structures such as a count-min sketch combined with a small heap, or the Space-Saving algorithm, find heavy hitters in fixed memory.
What the interviewer is listening for
- The size-k heap, and a correct explanation of why it is a min-heap.
- O(n log k) time and O(k) memory, and why that suits a stream.
- Alternatives with their trade-offs, and a sensible distributed design.
Common mistakes
- Using a max-heap of all n items.
- Sorting the full data set.
- Forgetting that frequency requires counting first, and that exact counts may not fit in memory.