Algorithm selectionIntermediate
Top 20 from an endless stream
Scenario
You receive millions of numbers as a stream — one at a time, never all in memory — and at any moment you must be able to report the 20 largest seen so far. Choose a data structure and justify it against the alternatives.
Your task
- Clarify the requirements: how often is "report" called relative to "insert"? Do you need the 20 sorted? Can values be removed?
- List at least three candidate approaches (sorted list, full sort, balanced BST, heap, quickselect) and reject the wrong ones with a reason.
- State the chosen structure, its invariant, and the per-operation cost.
- Extend: what if you also need the 20 *smallest*? What if the window is "last 1 million numbers" rather than "all time"?
Pattern RecognitionComplexity AnalysisProblem Clarification
Work it out
Write your analysis before revealing anything. The self-check below compares it against what a strong answer contains.
Reveal
Progressive — each section builds on the previous one.
Key observation
The fix
Edge cases
Complexity
What this tests
Self-check
Tick what your analysis covered. Be honest — this feeds your readiness profile.