Coding Interview: How Would You Maintain the Median of a Data Stream?

Prompt and context

The input is a continuous integer stream, not a one-time array. Support addNum(x) and findMedian() without sorting all values after every insert. The question tests whether the candidate can derive two heaps from the need to know the boundary between two ordered halves.

What the interviewer tests

The interviewer looks for heap roles, size balance, top-order invariants, even-length semantics, and duplicate handling. Strong answers clarify whether all values may be stored, numeric range, thread safety, and approximation, then prove O(log n) insertion, O(1) lookup, and O(n) space.

Questions to clarify

• Is the stream unbounded? May we store every item, or must we use a window or approximation?
• For an even count, is the median the average, lower median, or upper median?
• Can values exceed 64-bit integers, and can averaging overflow?
• Do we need deletion, undo, a time window, or concurrent calls?
• What should an empty stream return: an error, empty value, or a caller precondition?

30-second answer framework

“I maintain a max-heap low for the smaller half and a min-heap high for the larger half. Invariants are low.top <= high.top and a size difference of at most one. Insert into the appropriate heap, rebalance by moving one top item, and return the middle top or a safe average of both tops. Insertion is O(log n), lookup O(1), and space O(n).”

Step-by-step deep answer

Step 1: Fix median semantics

The common definition takes the unique middle value for odd length and averages the two middle values for even length. State this before coding. Approximate quantiles are a different problem.

Step 2: Define the heaps

low is a max-heap containing the lower half; high is a min-heap containing the upper half. Every value in low is no greater than every value in high; duplicates are fine when the invariant holds.

Step 3: Choose the insertion path

If low is empty or x <= low.top, push into low; otherwise push into high. Then move at most one top element to repair the size difference, avoiding a full scan.

Step 4: Keep sizes balanced

Keep low equal to or one larger than high. If low is two larger, move its top to high; if high is larger, move its top to low. The tops then represent the median boundary.

Step 5: Handle lookup and numeric safety

Return a clear error for an empty stream. For odd length return low.top; for even length average both tops in a wider type or with an overflow-safe formula.

Step 6: Prove complexity

Insertion performs a constant number of heap pushes/pops at O(log n). Lookup reads one or two tops at O(1). Together the heaps store n values, so space is O(n).

Step 7: Explain alternatives

Sorted-array insertion is O(n). An order-statistics tree supports logarithmic updates and rank queries but is more complex. A counting histogram fits a tiny value domain; a quantile sketch fits an unbounded stream when error is allowed.

Step 8: Validate boundary cases

Test empty, one value, even count, duplicates, negatives, monotonic input, and numeric extremes. After each insert assert size balance, top order, and median. For concurrency, test the lock around both heaps as one invariant.

Pseudocode

add(x):
    if low.empty() or x <= low.max(): low.push(x)
    else: high.push(x)
    if low.size() > high.size() + 1: high.push(low.pop())
    if high.size() > low.size(): low.push(high.pop())

median():
    if low.size() > high.size(): return low.max()
    return safe_average(low.max(), high.min())

Trade-offs and boundaries

Two heaps do not delete arbitrary old values efficiently; a sliding window needs lazy deletion or another structure. They also provide no persistence, distributed merge, or multi-machine consistency.

Rollout plan and evidence

Implement the heaps and edge tests first, then add overflow protection and metrics. Public interview material frames this as online order statistics; TechInterview and Intervu both present two heaps as the canonical streaming structure.

Pilot exit criteria

Boundary tests pass; invariants hold for random sequences; latency and memory fit budget; extremes do not overflow; and empty-stream behavior is explicit.

How to prove the gain is real

Compare throughput, p95 latency, peak memory, and result equality with a full-sort baseline under identical random seeds covering increasing, decreasing, duplicate, and extreme distributions.

Common mistakes and follow-ups

Sorting every value after insertion

That makes insertion O(n log n), which does not scale for a live stream. Two heaps maintain only the boundary information.

Balancing sizes without ordering tops

low.top <= high.top is also required. Without it, the top values are not the median boundary.

Ignoring even-length semantics

State whether the answer is an average, lower median, or upper median, and handle conversion and overflow.

How would you support a sliding window?

Mark expired values for lazy removal and clean them from heap tops, or use an order-statistics tree. Re-state the complexity and memory bound.

What if the stream cannot be stored?

Use a quantile sketch when error is acceptable. Exact median requires enough order information; general exact constant-space is not possible.

How do you make it thread-safe?

Use a read/write lock or single-threaded event loop around both heaps and their invariant. A lookup must not observe only one heap updated.