Holding the Center

A hard Python interview practice problem on DataDriven. Write the Python and run it against test cases, with instant feedback.

Domain
Python
Difficulty
hard
Seniority
L5

Problem

A latency monitor emits a reading after every request, and a live dashboard refreshes the median of all readings seen so far each time one arrives. Given stream, the readings in arrival order, return the running median after each reading, taking the average of the two middle values whenever an even number of readings has arrived. Each median comes back as a float, and a stream of a single reading reports that reading itself.

The middle value keeps moving as new data arrives.

Example 1

Input:

stream = [1,2]

Output:

[1,1.5]

Example 2

Input:

stream = [1,3,2]

Output:

[1,2,2]

Worked solution and explanation

What this really is

Strip the dashboard framing and this is the streaming-median problem: you need the middle of a growing multiset, recomputed on every arrival, without ever re-sorting. The trap is reaching for sorted(seen)[mid] inside the loop, which is O(n log n) per element and O(n squared log n) overall. What separates a senior answer is noticing you only ever need the two values straddling the middle, so you keep the lower half and the upper half as separate structures and read the boundary in constant time.

Break down the requirements

Step 1: Maintain two heaps: max-heap for the lower half, min-heap for the upper half

The max-heap (lo) holds elements at or below the median. The min-heap (hi) holds elements above it. Because heapq is a min-heap, negate every value going into lo so its top is the largest of the lower half.

Step 2: Route each value through both heaps

Push to lo first, then immediately move lo's top into hi. This guarantees every element in lo is smaller than every element in hi before you worry about sizes.

Step 3: Rebalance after each insertion

The heaps may differ in size by at most one. If hi ends up larger, move its top back into lo so lo is never smaller than hi.

Step 4: Read the median off the tops

If lo is the larger heap, its top is the median, and you wrap it in float() so an odd-count answer reports as a float like the even case. If the sizes are equal, average the two tops (division already yields a float). Both reads are constant time.

The solution

Two-heap streaming median tracker
import heapq

def compute_running_median(stream):
    lo = []  # max-heap (negated) for the lower half
    hi = []  # min-heap for the upper half
    result = []
    for num in stream:
        heapq.heappush(lo, -num)
        heapq.heappush(hi, -heapq.heappop(lo))
        if len(hi) > len(lo):
            heapq.heappush(lo, -heapq.heappop(hi))
        if len(lo) > len(hi):
            median = float(-lo[0])
        else:
            median = (-lo[0] + hi[0]) / 2
        result.append(median)
    return result

float(-lo[0]) keeps the odd-count median a float, matching the even-count average.

Common follow-up questions