ORIGINAL TECHNICAL PRACTICE
Keep the largest k items in a stream
Explain how to retain the largest k values when the stream cannot be sorted or stored in full.
Written for independent practice. The model answer presents one approach; clarify constraints and explain alternatives.
A REASONED APPROACH
Model answer.
Maintain a min-heap of at most k items. Its root is the smallest retained item, so a larger incoming value can replace it without keeping the rest of the stream.
Work through it
- Define behavior for k<=0, k larger than the stream, repeated values and ties involving records. State whether output must be sorted.
- Push until the heap contains k items. After that, replace the root only when an incoming item belongs in the retained set.
- At the end, sort only the retained items if the contract requires ordered output. Demonstrate why every discarded value is no larger than the smallest retained threshold at its processing time.
Tradeoffs to discuss
- Processing costs O(n log k) time and O(k) storage. A final sort adds O(k log k); a bounded integer domain may support a different counting approach.
Common pitfalls
- A heap is not a fully sorted array. Arbitrary tie-breaking can make record selection nondeterministic unless a secondary key is specified.