Find Median from Data Stream

Q: Why would an infra interview ask this?

Percentile latency is how services are monitored and how SLOs are written, and the median is the simplest percentile. This problem asks you to maintain one over a live stream, which is what a metrics pipeline does. Interviewers often follow up by asking how you would get a p99 over millions of samples, which leads to approximate structures.

Q: How do real monitoring systems compute p99 over huge streams?

They usually don't keep every sample. Histograms with fixed buckets (as in Prometheus) or sketches such as t-digest and HDR histograms store a compact summary and answer percentiles approximately, with bounded error and memory that doesn't grow with the stream.

Q: Why push onto low and then immediately move to high?

It routes the new value through both heaps so it lands on the correct side without an explicit comparison. Whatever comes out of low is the largest of the lower half plus the new value, so high only ever receives values at least as large as everything left in low.

hardHeaps (hard) Must-do

Latency samples arrive one at a time and you need the median of everything seen so far at any moment. Build a class MedianFinder with:

addNum(num): record one integer sample.
findMedian(): return the median of all samples recorded so far, as a float. With an odd count it is the middle value in sorted order; with an even count it is the average of the two middle values.

findMedian is only called after at least one sample. Both operations will be called many times, interleaved, so neither can afford to re-sort everything.

Examples

Example 1

Input: addNum(40), addNum(10), findMedian(), addNum(30), findMedian()

Output: [25.0, 30.0]

Explanation: After 10 and 40 the median is (10 + 40) / 2. After adding 30 the sorted samples are 10, 30, 40.

Example 2

Input: addNum(5), findMedian(), addNum(5), findMedian(), addNum(1), findMedian(), addNum(2), findMedian()

Output: [5.0, 5.0, 5.0, 3.5]

Explanation: Duplicates count separately. The last state is 1, 2, 5, 5, so the median is (2 + 5) / 2.

Hints

Approach

Two heaps. low is a max-heap holding the smaller half of the samples; high is a min-heap holding the larger half. Keep len(low) equal to len(high) or one more.

addNum(num):

Push num onto low, then move low's largest onto high. This guarantees everything in low is <= everything in high.
If high is now bigger than low, move high's smallest back to low.

findMedian: with an odd total, the median is the top of low; with an even total, it is the average of both tops.

Python's heapq is a min-heap only, so low stores negated values.

ComplexityTime addNum O(log n), findMedian O(1)Space O(n)

Python

import heapq
 
 
class MedianFinder:
    def __init__(self):
        self.low = []   # max-heap via negation: the smaller half
        self.high = []  # min-heap: the larger half
 
    def addNum(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 findMedian(self):
        if len(self.low) > len(self.high):
            return float(-self.low[0])
        return (-self.low[0] + self.high[0]) / 2
 
 
m = MedianFinder()
m.addNum(40)
m.addNum(10)
a = m.findMedian()
m.addNum(30)
print([a, m.findMedian()])
 
m = MedianFinder()
out = []
for x in [5, 5, 1, 2]:
    m.addNum(x)
    out.append(m.findMedian())
print(out)

Follow-up questions

Median of only the last k samples (a sliding window): how do you remove old values from the heaps? (Lazy deletion with a counter, or a balanced tree.)
If all samples are integers from 0 to 100, how can you make both operations O(1)? (Counting buckets.)

Frequently asked questions

Percentile latency is how services are monitored and how SLOs are written, and the median is the simplest percentile. This problem asks you to maintain one over a live stream, which is what a metrics pipeline does. Interviewers often follow up by asking how you would get a p99 over millions of samples, which leads to approximate structures.

They usually don't keep every sample. Histograms with fixed buckets (as in Prometheus) or sketches such as t-digest and HDR histograms store a compact summary and answer percentiles approximately, with bounded error and memory that doesn't grow with the stream.

It routes the new value through both heaps so it lands on the correct side without an explicit comparison. Whatever comes out of low is the largest of the lower half plus the new value, so high only ever receives values at least as large as everything left in low.

Problem statement