PPractick

The problem

A latency dashboard receives response times one at a time and must show the running median after every new value, at any moment. Keeping a sorted array costs O(n) per insert. Instead, split the values into two halves. A max-heap holds the smaller half and a min-heap holds the larger half, with sizes kept equal or the lower half one larger. The median is then either the lower half's top or the average of the two tops, and each insert is O(log n).

Example: addNum(1), addNum(2), findMedian() → 1.5, addNum(3), findMedian() → 2.0.

Function signature

class MedianFinder {
public:
    void addNum(int num);
    double findMedian();    // called only after at least one addNum
};

Test cases

Operations	Output	Explanation
add 1, add 2, median, add 3, median	1.5 2.0	LeetCode's example
add 5, median, add 15, median, add 1, median, add 3, median	5.0 10.0 5.0 4.0
add −1, −2, −3, −4, −5, median after each	-1.0 -1.5 -2.0 -2.5 -3.0	Negative values

(Confirm: the median of an even count is the average of the two middle values; values fit in 32-bit ints, but their sum may not, so add in floating point.)

How interviewers phrase it

• "Implement the MedianFinder class with addNum and findMedian" (LeetCode 295).

Clarifying questions to ask

1. How often is each operation called? (Up to 5·10⁴ calls, so O(log n) insert and O(1) median.)
2. How should an even count be handled? (Average the two middle values.)
3. What's the value range? (If values are bounded, say 0–100, a counting array gives O(1) inserts.)

Follow-ups to expect

1. "What invariants do the two heaps keep?"
2. "How does addNum keep them?"
3. "Why can't a single heap do it?"
4. "What if most values are in a small range?"
5. "Complexity?"

Related questions

• Kth largest element in a stream of running integers Hard
• Design Twitter Medium
• Minimize Max Distance to Gas Station Hard
• Implement Min Stack Hard
• LFU Cache Hard
• Merge K sorted Lists Hard

All 474 dsa interview questions

DSA mock interviews · System design interview questions · Free mock interview practice · Browse interviewers · Sign in