Classic two-heap problem. Use a max-heap for the lower half and a min-heap for the upper half.

The key is maintaining the balance: the heaps should differ in size by at most 1. On each insertion, add to the appropriate heap and rebalance if needed.

I coded it up in about 15 minutes. The interviewer then asked about follow ups:

1. What if 99% of numbers are between 0 and 100? Used a bucket-based approach with counting sort for the common case, falling back to heaps for outliers.

2. What about a distributed stream? Discussed using quantile sketches (t-digest) for approximate median computation across multiple nodes.

3. What if you need the median over a sliding window? This one was harder. Discussed using two balanced BSTs (or order-statistic trees) with lazy deletion.

Got through all three follow ups which I think was the deciding factor. The interviewer said most candidates only get through two.

Tip: practice the follow up variations, not just the base problem.