Prompt and context
You inherit a MedianFinder with a max-heap for the lower half and a min-heap for the upper half. It works for 1, 2, 3, yet fails on sequences such as 10, 1, 9, 2, duplicate-heavy input, and extreme integers. The task is to debug an existing implementation, not derive the standard data structure from scratch.
What the interviewer evaluates
- Whether you state invariants before changing code.
- Whether you can shrink a failing sequence and identify the first invalid state.
- Whether the repair handles empty queries, duplicates, and even-length overflow.
- Whether the proof and complexity match the code.
Clarifying questions to ask
- What should
findMedian()do before the first insertion? - Which heap may contain the extra element?
- What integer width does the API accept, and what type does the median return?
- May duplicates appear, and is concurrent access in scope?
Assume duplicates are valid, the lower heap may have one extra element, the query returns a floating-point value, and empty lookup raises a documented error. Concurrency is outside this coding task.
A 30-second answer
“I would instrument both heaps after every insertion and assert two invariants: their sizes differ by at most one with the lower heap larger, and every lower value is no greater than every upper value, which can be checked at the heap tops. I would minimize the first failing input, then repair insertion by pushing into the lower heap, moving its maximum to the upper heap, and moving the upper minimum back only when it is larger. Median lookup uses the lower top for odd size and an overflow-safe average of both tops for even size. Finally I would run a sorted-array oracle over exhaustive short sequences and adversarial extremes.”
Step-by-step deep dive
1. Make the failure observable
After each insertion, record the input prefix, both heap sizes, and both tops. Stop at the first broken invariant. Delta-debug the sequence by removing values while the failure remains. A four-value counterexample is more useful than a thousand random values.
2. Repair with one deterministic insertion path
Use the lower heap as the entry point. Push x, move its maximum to the upper heap, then move the upper minimum back if the upper heap became larger. This sequence restores ordering before size. With a language library that provides only a min-heap, store negated values in the lower heap and keep the sign conversion at the boundary.
3. Make lookup safe
Reject lookup when both heaps are empty. For odd count, return the lower maximum. For even count, convert both endpoints to a wider or floating type before adding; (a + b) / 2 can overflow in a fixed-width integer type even when the median is representable.
4. Prove and test the repair
Moving the lower maximum to the upper side guarantees the remaining lower values do not exceed the moved boundary. Moving one upper minimum back restores the chosen size rule without breaking ordering. Each insertion performs a constant number of heap operations, so it is O(log n); lookup reads one or two tops in O(1), and storage is O(n).
Use a sorted-list oracle after every prefix. Cover empty lookup, one value, two extremes, ascending, descending, alternating low/high, all duplicates, negative values, and many transitions between odd and even size.
A strong sample answer
“I would not patch the branch that happened to fail. I would first assert lower.size == upper.size or lower.size == upper.size + 1, plus max(lower) <= min(upper) whenever both exist. On each add, I push into lower, move its maximum to upper, then move the upper minimum back only if upper is larger. That makes ordering restoration independent of the previous input pattern.
findMedian rejects an empty structure. An odd-sized stream returns the lower top; an even-sized stream converts both tops before averaging so extreme integers cannot overflow. I would compare every prefix against a sorted-array oracle for exhaustive short sequences drawn from negative, zero, duplicate, and extreme values. The core implementation remains O(log n) per add, O(1) per query, and O(n) space.”
Common mistakes
- Balancing sizes only → the heaps may contain crossed values → assert top ordering as a separate invariant.
- Choosing a branch from the incoming value only → previous heap state can still be invalid → use a deterministic move-between-heaps sequence.
- Averaging in the input integer type → extreme endpoints may overflow → widen before addition.
- Testing only sorted unique values → duplicates and alternating extremes hide branch errors → use prefix oracles and adversarial sequences.
- Claiming
O(1)insertion → heap pushes and pops are logarithmic → count the actual heap operations.
Follow-up questions and responses
How would you find the smallest failing input?
Keep deleting one element or one contiguous chunk and rerun the invariant checks. Preserve the shortest prefix whose final insertion first violates ordering or size, then inspect only that transition.
Why do duplicates not need special handling?
The invariant uses <=, so equal values may live on either side. Heap size determines which equal copy contributes to the median; identity does not matter.
How would you test without trusting another heap implementation?
For small inputs, copy the prefix, sort it, and compute the mathematical median directly. Exhaust all sequences over a tiny alphabet, then add fixed-width extremes and larger randomized cases.
Does this support a sliding window?
No. Removing an arbitrary expired value needs indexed deletion or lazy-deletion counters in both heaps. That is a different task and should not be hidden inside this repair.