Coding interviews
Reveal answer and reasoning
Maintain the exact median of all integers received so far. The lower half is a max-heap and the upper half a min-heap. Their sizes differ by at most one, with the lower half owning the extra element. For an even count return the average of the two boundary values as decimal, and reject querying an empty stream. The two invariants are ordering and balance: every lower-half value is no greater than every upper-half value, and low.Count equals high.Count or exceeds it by one.
The median is then determined by their boundary roots. Choosing the lower heap to own the extra value simplifies odd-length queries.
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. PriorityQueue is a min-heap abstraction, so the lower heap uses a reversed comparer rather than negated priorities. Retaining duplicate values is necessary because median depends on multiplicity.
The two heaps do not deduplicate observations, and their O(n) storage grows even when every incoming value is identical.
What a strong answer covers
- Maintain the exact median of all integers received so far.
- Insertion first chooses a side by comparison with low.Peek, then moves at most one root to repair size imbalance.
- Each insertion performs a bounded number of heap operations, costing O(log n) time; reading the median is O(1).
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.