Coding interviews
Reveal answer and reasoning
An approximate quantile summary needs a stated error model, such as rank error, and a clear time window. If the requirement is an exact sliding median, expiration changes the problem and requires indexed removal or delayed-deletion bookkeeping. Neither requirement can be satisfied simply by capping one of these heaps and discarding arbitrary values.
Each insertion performs a bounded number of heap operations, costing O(log n) time; reading the median is O(1). Both heaps together retain all n input values, so this exact unbounded-history structure uses O(n) storage. A streaming interface is not automatically constant-memory. Negating an integer priority to simulate a max-heap fails at int.MinValue. The comparer reverses CompareTo instead, avoiding subtraction and negation overflow.
Sliding-window medians require removing expired values or another data structure; this implementation handles append-only history only.
The interview proof should connect the two invariants to the returned median before listing complexity. Then trace an insertion that crosses heaps and an even-count average at the numeric extremes. A senior answer notices that exact all-history statistics retain unbounded history and asks whether approximation or windowing is acceptable. The fixture uses the real framework priority queue and a safe comparison primitive, so no custom heap mechanics are being hidden.
Independent prefix-oracle checks are particularly valuable because a final median can look correct even after an earlier balancing error. An empty-state query must be tested before any insertion because Peek has no valid root then; the method deliberately throws a named InvalidOperationException rather than inventing a median of zero.
What a strong answer covers
- An approximate quantile summary needs a stated error model, such as rank error, and a clear time window.
- Each insertion performs a bounded number of heap operations, costing O(log n) time; reading the median is O(1).
- Negating an integer priority to simulate a max-heap fails at int.MinValue.
Common pitfall
Negating an integer priority to simulate a max-heap fails at int.MinValue. The comparer reverses CompareTo instead, avoiding subtraction and negation overflow. Sliding-window medians require removing expired values or another data structure; this implementation handles append-only history only.
Follow-up questions
- Test duplicates, a single minimum integer, an even pair spanning both integer extremes and querying before the first insertion. Hint: check size and ordering invariants after every insertion, not just the final printed median.
- How would expiration of the oldest value change the append-only median design?
Self-review
Choose what to revisit. These marks are your own assessment and are separate from lesson completion.