Find median from data stream with two heaps — invariant and rebalancing?

Q: Find median from data stream with two heaps — invariant and rebalancing?

**Target Audience:** Developers who have seen the two-heap median solution in Python and want to explain why it is correct. **Difficulty:** Medium **Language:** Python 3 > **How to read this doc:** every idea is explained in plain words first. When a word appears that an interviewer will expect you to know, it is tagged `📌 Interview term:` with a one-line definition, and every tagged term is collected in the Quick Glossary at the end. Every program on this page was actually run, and the output you see in the **Verified** section is copied from that run. ## 1. Why This Even Matters — A Story First Picture a seesaw in a playground with a line painted across the middle. Children arrive one by one. Smaller children sit on the left, bigger ones on the right, and a teacher keeps the two sides with the same number of children, or one extra on the left. The child closest to the middle line on the left side, together with the one closest to it on the right, tells you where the middle of

The problem

Question presented to candidate: "You are keeping a running median with two heaps in Python. State the invariant precisely, explain why it gives you the median, and show how add_num restores it after every insert. Why is one move between the heaps always enough?"

What a strong answer should cover:

The order rule (max of the lower half ≤ min of the upper half) and the size rule (sizes equal, or the lower half has one more).
Why the two rules together put the median at the tops: positions |low| and |low| + 1 in sorted order.
The routing step and the case analysis showing one move restores the size rule; the order rule survives both routing and the move.
The two common strategies (compare-first vs push-through) and their cost in heap operations.
Python details: heapq is min-only, so the lower half stores negated values and every move must negate exactly once; / 2, not // 2.

Code / implementation expected: Optional — an add method plus an invariant_ok check in Python 3.

heap
design
Amazon

Try it yourself

Sketch your approach before you read the solution. That is what the interview tests.

Stuck? Get a hint.

A short nudge toward the approach. It will not give the answer away.

Solution

Target Audience: Developers who have seen the two-heap median solution in Python and want to explain why it is correct.
Difficulty: Medium
Language: Python 3

How to read this doc: every idea is explained in plain words first. When a word appears that an interviewer will expect you to know, it is tagged 📌 Interview term: with a one-line definition, and every tagged term is collected in the Quick Glossary at the end. Every program on this page was actually run, and the output you see in the Verified section is copied from that run.

1. Why This Even Matters — A Story First

Picture a seesaw in a playground with a line painted across the middle. Children arrive one by one. Smaller children sit on the left, bigger ones on the right, and a teacher keeps the two sides with the same number of children, or one extra on the left. The child closest to the middle li

The solution is hidden so you can try first

13 min read · 14 sections

Python code

Edit the code and run it here. Each printed line with an expected value becomes a test.

PythonTrace: route, rebalance and median for seven adds

Practice

PythonInvariant check on 5000 adds, two strategies, overflow pairs

Practice

Discussion

Other approaches, follow-ups and how it went in real interviews.

Sign in to join the discussion.

No comments yet. Share how you would answer it.

The solution is hidden so you can try first

Keep your momentum going.