Top K from a stream
“You receive numbers one at a time and must report the K largest at any point. How do you approach it?”
What this tests
- Whether the candidate distinguishes streaming (bounded memory) from batch settings.
- Whether they pick a min-heap of size
Kand can explain why min, not max. - Ability to state
O(n log k)time andO(k)space and compare with alternatives. - Awareness of quickselect for the batch case.
Strong answer
The stream constraint means I cannot store everything; I need O(k) state. The structure is a Min-Heap of size K holding the current top-K. The heap's minimum is the *weakest member of the elite*: when a new number arrives, if it exceeds the minimum I pop the minimum and push the new number; otherwise I ignore it. Each arrival costs O(log k), so n arrivals cost O(n log k) with O(k) memory.
Why a min-heap and not a max-heap? Because the operation I need is "evict the smallest of the kept set", and a min-heap exposes exactly that in O(1) peek and O(log k) pop. A max-heap of everything would answer "largest overall" but costs O(n) memory and cannot evict the weakest efficiently.
In a batch setting with all n numbers available, Quickselect finds the K-th largest in expected O(n) and partitions the top K beside it; sorting is O(n log n). A strong candidate compares: heap is streaming-friendly and gives sorted output of the top K cheaply; quickselect is faster for one-shot queries but not incremental. If K is close to n, keep a min-heap of the n - K smallest instead.
Green flags · Red flags
- Chooses min-heap and explains "smallest of the kept set" as the reason.
- States
O(n log k)time,O(k)space, and contrasts withO(n log n)sorting. - Mentions quickselect for the batch variant with its expected
O(n)bound. - Asks about
Krelative ton, duplicates, and whether the top-Kmust be reported sorted. - Extends to top-
Kfrequent with a count map plus heap or bucket sort.
- Proposes a max-heap of all elements and calls it
O(k)space. - Sorts the entire stream on every query.
- Cannot explain why the heap size stays at
K. - Confuses
O(n log k)withO(k log n).
Follow-up questions
Each follow-up changes a requirement; the right answer changes with it.
K frequent elements from a fixed array.K = 1?