How do you find the median from a data stream? | Interview Question

Q: How do you find the median from a data stream?

**Target Audience:** Developers preparing for coding interviews who know arrays and basic classes in Python; heaps are explained as we go. **Difficulty:** Hard **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 A radio quiz show reads out contestants' scores one at a time, and after every score the host asks the studio: "What is the middle score so far?" Nobody writes the scores down in order. If you kept every score on a scrap of paper and re-sorted the pile each time, you would be shuffling papers longer and longer as the night goes on. A smarter assistant keeps **two piles**.

The problem

Question presented to candidate: "Numbers arrive one at a time. Design a Python class with add_num(x) and find_median(), where find_median returns the median of everything added so far. Both calls happen many times, so tell me the cost of each."

What a strong answer should cover:

Why sorting on every query (O(n log n)) and keeping a sorted list (O(n) per insert) are too slow for long streams.
Two heaps: a max-heap for the lower half and a min-heap for the upper half; O(log n) add, O(1) median.
The invariant: every number in the lower half ≤ every number in the upper half, and the sizes differ by at most one.
Python details: heapq is a min-heap only, so the lower half stores negated values; use / 2 (true division) for the even case, not // 2.
Follow-ups: values in a small range (counting buckets), removals (sliding window), percentiles other than 50%.

Clarifying questions expected:

For an even count, average the two middle values or return the lower one?
What range can the values take, and can they be removed?

Code / implementation expected: Yes — a MedianFinder class built on two heapq lists, in Python 3.

heap
design

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 preparing for coding interviews who know arrays and basic classes in Python; heaps are explained as we go.
Difficulty: Hard
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

A radio quiz show reads out contestants' scores one at a time, and after every score the host asks the studio: "What is the middle score so far?" Nobody writes the scores down in order. If you kept every score on a scrap of paper and re-sorted the pile each time, you would b

The solution is hidden so you can try first

15 min read · 15 sections

Python code

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

PythonMedianFinder: the median after every add (3 streams)

Practice

PythonSort every time vs sorted insert vs two heaps vs buckets

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.