Problem statement
Design the object model and public API for a component that ingests a stream of numbers and can report the running median at any moment in O(log n) per insert and O(1) per query.
Operating context. One process, in-memory. Numbers arrive one at a time and are never removed in v1 (an append-only core; sliding-window removal is an extension). The canonical approach balances a max-heap holding the lower half against a min-heap holding the upper half. It lives inside an analytics pipeline computing rolling summary statistics on a metric feed.
Out of scope. Persistence, distributed or partitioned streams, arbitrary percentiles other than the median (name the quantile-generalization seam), approximate-quantile sketches, and out-of-order timestamp handling.
What to produce. The class model (the two heaps, a MedianStream facade, and an injectable comparator), the public API (add, median, count, min, max, reset), the size-balance invariant that keeps the two heaps within one element of each other, and how an even-count median averages the two heap tops — state the balance invariant explicitly.
Functional requirements
- Add a number to the stream, routing it into the lower-half or upper-half heap.
- Rebalance the two heaps so their sizes differ by at most one after every insert.
- Report the current median, averaging the two heap tops when the count is even.
- Report the count of numbers seen so far and the running minimum and maximum.
- Reset the stream to empty for reuse.
Non-functional requirements
- Each insert is O(log n) and each median query is O(1).
- The size-balance invariant between the two heaps holds after every insert.
- The heap implementation is pluggable behind an interface so it can be swapped or instrumented.
- The ordering comparator is injectable, decoupling numeric order from the balancing logic.
- The component is unit-testable deterministically without threads or a wall-clock.
Topics
- System Design LLD
- Ds Heap
- Streaming Statistics
- Oop Solid
- Patterns Strategy