Coding Interview: Find the Median from a Data Stream

Problem and Applicable Context

Design MedianFinder with two operations:

• addNum(num) adds an integer to the stream.
• findMedian() returns the median of every value seen so far. With an odd count, it returns the middle value; with an even count, it returns the average of the two middle values.

Assume inserts only, with no deletion, and that findMedian() is called only after at least one insertion. Inputs may include negative numbers, duplicates, and signed 32-bit integers, with at most 50,000 operations. The target is O(log n) per insertion, O(1) per query, and O(n) space.

For example, after inserting 5, 2, 10, 4, the running medians are 5, 3.5, 5, 4.5. Sorting on every query is correct but costs O(n log n) per query. Keeping an array fully sorted makes the query O(1), but inserting in the middle still shifts O(n) elements.

Public interview-preparation material in 2026 continues to present this as a representative two-heaps coding problem. It applies to general software, backend, data, and infrastructure coding rounds. The useful signal is not recalling the phrase “max-heap plus min-heap.” It is deriving the structure from the query, stating both invariants, and proving why a fixed transfer sequence preserves the partition.

What the Interviewer Is Evaluating

The first signal is choosing a structure from the operation mix. A median depends only on the middle of the sorted order, so maintaining the complete order is unnecessary. To answer in O(1), the one or two middle candidates must always be exposed at directly readable positions. Heap tops provide exactly that boundary access.

The second signal is maintaining both partition and balance:

1. A max-heap lower stores the smaller half, a min-heap upper stores the larger half, and every

value in lower is at most every value in upper.

1. lower has the same size as upper or exactly one extra element.

Neither condition is sufficient alone. Similar sizes do not prevent values from being placed in the wrong half. Correct partition order does not prevent one heap from growing much larger, which would make its top cease to represent the middle.

The third signal is precise complexity analysis. An insertion performs a constant number of heap operations, each O(log n). A query reads one or two tops, so it is O(1). The structure still stores every input and therefore uses O(n) space. “Streaming” means online updates here, not constant memory.

Finally, the interviewer looks for validation beyond the sample. A strong answer tests the first element, even and odd counts, duplicates, all-negative values, increasing and decreasing sequences, and integer extremes. It also compares random operation sequences against a slow, obviously correct sorted-list model.

Clarifying Questions Before Answering

• Are there only inserts, or must old values be deleted? Two ordinary heaps are sufficient for inserts only. A sliding window needs lazy deletion or an ordered multiset.
• Can the query run on an empty stream? This prompt says no. A production API should return an optional value or raise an explicit error instead of reading an empty top.
• Are inputs integers or floating-point values? This version uses integers. If floating-point NaN is allowed, the values do not form a normal total order, so rejection or ordering semantics must be defined.
• How is the median defined for an even count? This prompt uses the arithmetic mean of the two middle values, so the return type must represent fractions.
• Must the result be exact? Yes. An unbounded stream under a fixed memory budget requires an approximate quantile contract instead.
• Can averaging overflow? Python integers do not overflow. Fixed-width languages should promote both operands before addition and division.
• What is the query-to-insert ratio? Two heaps fit frequent queries. If the median is requested only once after all input arrives, collecting and sorting is usually simpler.
• Is concurrent access required? The implementation is single-threaded. A concurrent version must make transfers and queries observe one state of both heaps.

30-Second Answer Framework

“I will keep the smaller half in a max-heap called lower and the larger half in a min-heap called upper. Every value in lower must be at most every value in upper, and lower has either the same size or one extra element. On insertion, I first push into lower, move its maximum to upper to restore partition order, and move upper's minimum back if upper became larger. For an odd count, the median is the top of lower; for an even count, it is the average of both tops. Insertion uses a constant number of O(log n) heap operations, the query is O(1), and space is O(n).”

Step-by-Step Deep Dive

Step one: compare baseline approaches and locate the bottleneck.

Binary search finds an array insertion index in O(log n), but it does not remove the O(n) shifting cost. A regular balanced tree preserves order, but without subtree sizes it cannot select the kth element directly. Two heaps retain only the two boundaries needed for the median, making them the smallest complete structure for this contract.

Step two: rewrite the median as one or two heap tops.

Let lower contain the smaller half in a max-heap, exposing that half's largest value. Let upper contain the larger half in a min-heap, exposing that half's smallest value. Allow lower to have one extra element:

Odd total:  lower has one extra, median = max(lower)
Even total: heaps have equal sizes, median = (max(lower) + min(upper)) / 2

The broadly available Python heapq interface is based on min-heaps. To keep the implementation portable across common Python versions, store negated values in lower. A logical maximum x becomes the smallest stored negative value -x, so -lower[0] is the maximum of the lower half.

Step three: use a fixed push, transfer, and rebalance sequence.

Instead of branching over every possible destination for the new value, always:

1. Push the negated num into lower.
2. Pop the logical maximum of lower and push it into upper.
3. If upper is now larger, move its minimum back to lower.

import heapq


class MedianFinder:
    def __init__(self) -> None:
        self.lower = []  # Negated max-heap containing the smaller half
        self.upper = []  # Min-heap containing the larger half

    def add_num(self, num: int) -> None:
        heapq.heappush(self.lower, -num)

        largest_lower = -heapq.heappop(self.lower)
        heapq.heappush(self.upper, largest_lower)

        if len(self.upper) > len(self.lower):
            smallest_upper = heapq.heappop(self.upper)
            heapq.heappush(self.lower, -smallest_upper)

    def find_median(self) -> float:
        if not self.lower:
            raise ValueError("median is undefined for an empty stream")

        if len(self.lower) > len(self.upper):
            return float(-self.lower[0])

        return (-self.lower[0] + self.upper[0]) / 2.0

This sequence performs an apparently extra transfer, but it removes several error-prone cases. Another valid implementation compares num with -lower[0], chooses a heap, and then rebalances. Both have the same asymptotic cost. In an interview, prefer the version whose invariants you can prove and review reliably.

Step four: prove the order invariant.

Assume before insertion that every value in lower is at most every value in upper. After the new value is temporarily pushed into lower, only that new value can be in the wrong half. Pop the maximum of the enlarged lower:

• Every value left in lower is at most the popped value.
• Every old lower value was already at most every old upper value.
• Therefore, after adding the popped maximum to upper, every new lower value is still at most

every new upper value.

After that transfer, upper may have one extra element. Moving its minimum back to lower preserves order: the moved value is at most everything remaining in upper and is no smaller than the old lower boundary. The heaps then have equal sizes or lower has one extra.

Both invariants hold for two empty heaps. Each insertion preserves them, so by induction the tops represent the middle positions after any operation sequence.

Step five: trace a sequence that crosses the partition.

Insert 5:  lower = [5]       upper = []        median = 5
Insert 2:  lower = [2]       upper = [5]       median = 3.5
Insert 10: lower = [5, 2]    upper = [10]      median = 5
Insert 4:  lower = [4, 2]    upper = [5, 10]   median = 4.5

A heap's backing array is not fully sorted. [4, 2] means only that 4 is the max-heap top. Debug checks should verify heap order, the two tops, and the cross-heap invariant rather than compare the backing arrays as sorted lists.

Step six: calculate complexity and identify when a simpler approach wins.

add_num performs at most five pushes or pops. Each heap operation is O(log n), so a constant number remains O(log n). find_median reads lengths and heap tops in O(1). Every value lives in exactly one heap, producing O(n) space.

If a product collects one batch and asks for one median at the end, storing and sorting the array is shorter and may have better contiguous-memory behavior. Maintaining an online structure is unnecessary. If every value is in the fixed range 0 through 100, an array of 101 counts gives O(1) insertion and a scan of a fixed 101 buckets, also constant for that fixed domain.

Step seven: close the loop with deterministic cases and randomized differential testing.

At minimum, test:

For a randomized test, add each generated integer to both MedianFinder and a reference array. Sort the reference and calculate its middle after every insertion. Compare both results and assert that len(lower) equals len(upper) or is one greater. The slow model is unsuitable for the target performance but excellent as a correctness oracle.

High-Quality Sample Answer

“I would first confirm that this is an insert-only exact median and that queries do not occur on an empty stream. If old window elements must be deleted, ordinary heaps cannot remove arbitrary values efficiently, so the design changes.

For constant-time queries, I want the middle of the sorted order continuously exposed at structure boundaries. I will use a max-heap lower for the smaller half and a min-heap upper for the larger half. Two invariants matter: every value in lower is at most every value in upper, and lower has the same size or one extra.

On insertion I use a fixed three-step sequence. Push the new value into lower, move lower's maximum to upper to restore the partition, and move upper's minimum back if upper became larger. Both invariants then hold again. With an odd count, lower has the extra value and its top is the median. With an even count, I average both tops.

Insertion performs a constant number of heap operations, so it is O(log n). The query reads tops in O(1), and retaining every value costs O(n) space. I would test one element, even counts, duplicates, negative values, monotonic input, and integer extremes, then run randomized differential tests against a sort-on-every-step model. If values are limited to 0 through 100, I would use 101 counters; if there is only one final query, I would simply sort.”

Common Mistakes

• Balance only the heap sizes → values can cross the partition and the tops are not the two middle values → maintain both order and size invariants.
• Put the smaller half in a min-heap → its top is the global minimum, not the lower half's maximum → use a max-heap for the smaller half.
• Return one top for an even count → the median definition is wrong → average both tops when sizes are equal.
• Add fixed-width integers before conversion → two large values can overflow first → promote both operands before adding and dividing.
• Call sorted-array insertion O(log n) → finding the index is fast but shifting remains O(n) → separate search cost from mutation cost.
• Treat Python's heap array as fully sorted → debugging assertions become invalid → depend only on the root and parent-child heap property.
• Read index zero from an empty heap → failure occurs at an unclear boundary → forbid empty queries or return an optional value explicitly.
• Claim the online algorithm uses constant space → both heaps retain all inputs → state O(n) space for an exact median.
• Reuse the same code for a sliding window → expired values can remain at a top and corrupt the result → add lazy deletion and valid sizes, or use an ordered multiset.
• Test only the sample → negation, duplicate, and rebalance bugs may not trigger → combine edge cases with randomized differential testing.

Follow-Up Questions and Responses

Follow-up 1: What changes if every integer is between 0 and 100?

Keep an array of 101 counts and the total element count. Insertion increments one bucket in O(1). To query, scan the buckets until reaching the one or two middle ranks. The scan and space are constant for this fixed domain. If the range grows with the input, the scan is O(R) for range size R and should no longer be described as constant.

Follow-up 2: What if 99% of values are between 0 and 100 but the rest are arbitrary?

Keep the 101 counters for in-range values and order-statistic structures for values below 0 and above 100. Their counts determine whether a target rank lies in the lower outliers, fixed range, or upper outliers; then select within the relevant structure. Ordinary heaps do not support arbitrary rank selection, so the 99% statement alone does not justify constant-time queries. An adversarial prefix can still place the median rank among outliers.

Follow-up 3: How would you compute the median of the latest k values?

Window movement requires deleting the outgoing value. Binary heaps cannot locate an arbitrary entry efficiently. A common solution adds a delayed-deletion count map and tracks valid sizes for both heaps. Mark an outgoing value logically deleted, and physically pop it only when it reaches a top; prune both tops before reading the median. Updates are amortized O(log k), while top lookup remains O(1). A balanced multiset with duplicate support is simpler when the language provides it.

Follow-up 4: Can a fixed-memory algorithm return the exact median of an unbounded stream?

In general, not for arbitrary integer streams. A discarded historical value may later determine the middle rank. The contract must change to an approximate quantile, using a quantile sketch with an explicit rank-error guarantee, confidence requirement, and merge behavior. That is a different answer from the exact two-heaps structure.

Follow-up 5: How would you support concurrent insertions and queries?

The two heaps form one logical state. The simplest correct extension protects the complete addnum and findmedian operations with the same mutex, preventing a query from observing the moment after a value leaves lower but before it enters upper. A read-heavy service could publish immutable median snapshots, but the snapshot interval introduces a freshness trade-off that belongs in the API contract.

Follow-up 6: Can medians from several shards be combined into a global median?

No. A shard median loses its shard's size and distribution; even a weighted average of shard medians is not the global median. An exact result requires a structure that can answer global rank, such as aggregating counts over a bounded domain and performing distributed selection. An approximate result can use mergeable quantile summaries. Precision and latency requirements must be chosen before the global structure.