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.
Must do 5
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.
Must hold 5
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.