Systematic designAdvanced
Running median of a stream
Scenario
Design a component that ingests a stream of numbers and can return the median of everything seen so far at any time. Ingest must be fast; queries are frequent. Then extend it to a *sliding* median over the last w values.
Your task
- Define the median precisely for even and odd counts.
- Reject the naive designs: re-sorting, insertion into a sorted list, a single heap. Give the cost of each.
- Present the two-heap design: invariants, insertion procedure, rebalancing, and query.
- Handle the sliding-window extension: what breaks, and what structure fixes it?
- State complexities and mention when a completely different approach (bucketed counts) is better.
Systematic ReasoningImplementationComplexity AnalysisEdge Cases
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.