How would you maintain a running median over a stream of incoming values, and why is a two-heap design the standard approach rather than keeping a sorted list?
technical-conceptual · Senior level · software-engineering
What the interviewer is really asking
Assesses whether the candidate can design the two-heap (max-heap/min-heap) running-median structure, reason about the rebalancing invariant and its O(log n) insert versus a sorted list's O(n) insertion, and handle the parity and removal edge cases.
What to say
- Describe the structure: a max-heap holds the lower half, a min-heap holds the upper half; the median is the max-heap's top (odd count) or the average of both tops (even count), so reading the median is O(1).
- State the rebalancing invariant on insert: push to the appropriate half by comparing to the current median, then move one element across if the heap sizes differ by more than one — each insert is O(log n) because it's a couple of heap operations.
- Justify it over a sorted list: a sorted array/list gives O(1) median read but O(n) insertion due to the shift to keep it sorted, whereas the two heaps give O(log n) inserts and O(1) median — the right trade for a high-throughput stream; note that supporting deletions (sliding window) needs lazy deletion or an order-statistics tree.
What to avoid
- Keeping a fully sorted list and paying O(n) per insertion to maintain order on a high-throughput stream.
- Forgetting the rebalancing step, so the heaps drift out of size balance and the top of one heap is no longer the median.
- Ignoring the even/odd parity rule for reading the median, or assuming the simple two-heap design supports arbitrary deletions without extra machinery.
Example answers
Strong: I keep two heaps: a max-heap for the lower half and a min-heap for the upper half, with their sizes differing by at most one. On each value I push to the correct side based on the current median, then rebalance by moving one element across if a heap got two ahead. The median is the larger heap's top, or the average of both tops when counts are equal — O(1) to read, O(log n) to insert. A sorted list reads the median in O(1) but costs O(n) per insert because you shift to stay sorted, which is too slow for a busy stream. If I also need to evict old values for a sliding window, I'd add lazy deletion or switch to an order-statistics tree.
Weak: I'd keep the numbers in a sorted list and on each insert put the value in the right spot, then read the middle element. Insertion keeps it sorted so the median is always just the center.