L3 · FAANGHeaps & streams~20 min · 4 tests

Find the Median From a Data Stream

Keep a running median with two heaps — a max-heap for the low half and a min-heap for the high half — giving O(log n) add and O(1) median. FAANG design.

The problem

Implement MedianFinder:

add(num) adds a number from the stream
median() returns the median of everything added so far, as a float

add should be O(log n) and median O(1).

Examples

Example 1

Input

run_ops(MedianFinder, [], [["add", 1], ["add", 2], ["median"], ["add", 3], ["median"]])

Expected output

[None, None, 1.5, None, 2.0]

Example 2

Input

run_ops(MedianFinder, [], [["add", 5], ["median"]])

Expected output

[None, 5.0]

+ 2 hidden tests on Submit.

Edge cases to ask about

One number
Negative numbers
Even vs odd count

Hints

0/3

How an interviewer scores this

0/9

1. Understand the problemRestate it, ask about edge cases and input size.
2. Write a brute-force solutionCorrect first, clever later.
3. Get the correct outputautoAll visible examples pass.
4. Analyse time complexityautoCommit to a Big-O in the Complexity Lab.
5. Analyse space complexityautoExtra memory, not the input.
6. Identify the bottleneckautoMeasure your code — where does it bend?
7. OptimiseUsually: a set or dict instead of a scan.
8. Explain why it worksSay it out loud to Solvi.
9. Test the edge casesautoSubmit passes every hidden test.

Python 3.13 · MedianFinder

import heapq

class MedianFinder:
    def __init__(self):
        pass

    def add(self, num):
        pass

    def median(self):
        pass

⌘/Ctrl + Enter runs the examples

Your code runs in real CPython inside your browser — nothing is sent anywhere. The first run downloads the interpreter (about 6 MB, once). Your code is saved on this device as you type.

Complexity Lab

What does this cost as n grows?

Interviewers score the analysis as much as the code. Commit to an answer first — then check it, and read why.

Time complexity of the optimal solution

Space complexity (extra memory)

Pick both to reveal the answer.

From brute force to optimal

The progression an interviewer wants to hear, one step at a time.

Approach	Time	Space	Idea
Sorted list with insort	O(n) add	O(n)	Binary search is O(log n) but the insert shifts elements.
bestTwo heaps	O(log n) add, O(1) median	O(n)	low holds the smaller half (max-heap), high the larger (min-heap).

Walkthrough of the optimal approach (try it yourself first)

low is a max-heap (store negatives) of the smaller half; high is a min-heap of the larger half. On add, push into low, move its largest to high (keeps every low value ≤ every high value), then rebalance so low has the same size or one more. The median is low's top, or the average of both tops.

Complexity: O(log n) time, O(n) space. add() does a constant number of heap pushes/pops (O(log n) each); median() reads the two heap tops.

Reveal the reference solution

import heapq

class MedianFinder:
    def __init__(self):
        self.low = []     # max-heap via negated values
        self.high = []    # min-heap

    def add(self, num):
        heapq.heappush(self.low, -num)
        heapq.heappush(self.high, -heapq.heappop(self.low))
        if len(self.high) > len(self.low):
            heapq.heappush(self.low, -heapq.heappop(self.high))

    def median(self):
        if len(self.low) > len(self.high):
            return float(-self.low[0])
        return (-self.low[0] + self.high[0]) / 2

The brute force, for comparison

import bisect

class MedianFinder:
    def __init__(self):
        self.values = []

    def add(self, num):
        bisect.insort(self.values, num)        # O(n) insert

    def median(self):
        v, n = self.values, len(self.values)
        return float(v[n // 2]) if n % 2 else (v[n // 2 - 1] + v[n // 2]) / 2

Follow-ups interviewers ask

All numbers are 0–100: O(1) add with counting.
Sliding-window median.

Frequently asked interview questions

Core interview concepts, complexities, and follow-ups scored by hiring teams.

What is the time complexity of Find the Median From a Data Stream in Python?

The optimal solution runs in O(log n) time and O(n) auxiliary space. add() does a constant number of heap pushes/pops (O(log n) each); median() reads the two heap tops.

What is the brute-force approach, and how do you optimise it?

Sorted list with insort: O(n) add time, O(n) space. Binary search is O(log n) but the insert shifts elements. Two heaps: O(log n) add, O(1) median time, O(n) space. low holds the smaller half (max-heap), high the larger (min-heap).

What follow-up questions do interviewers ask about Find the Median From a Data Stream?

All numbers are 0–100: O(1) add with counting. Sliding-window median.