Maintain the Median of an Integer Stream
Company: StackAdapt
Role: Machine Learning Engineer
Category: Coding & Algorithms
Difficulty: easy
Interview Round: Technical Screen
# Maintain the Median of an Integer Stream
Design a `MedianFinder` with two operations:
- `addNum(value)` adds one integer from a stream.
- `findMedian()` returns the median of all values added so far.
For an odd number of values, return the middle value in sorted order. For an even number, return the arithmetic mean of the two middle values. `findMedian()` will only be called after at least one insertion.
### Constraints & Assumptions
- Values may arrive in any order and duplicates are allowed.
- The full stream is not known in advance.
- Re-sorting all prior values after every insertion is not an acceptable steady-state strategy.
### Clarifying Questions to Ask
- What numeric type should represent the average of two middle integers?
- Is the workload dominated by insertions, median queries, or a balanced mix?
- Will the data structure run in one process, or must updates be merged across machines?
```hint Maintain two ordered halves
Keep the lower half able to reveal its maximum and the upper half able to reveal its minimum.
```
```hint State the balancing invariant
The two halves should differ in size by at most one, with every lower-half value no greater than every upper-half value.
```
### Evaluation Criteria
- A max-heap for the lower half and a min-heap for the upper half.
- Correct rebalancing after every insertion, including duplicates and negative values.
- Constant-time median lookup after `O(log n)` insertion work.
- Linear storage for the values retained by the two heaps.
### Extensions to Discuss
- How would you generalize the structure to answer an arbitrary percentile rather than only the median?
- What changes if values are known to lie in a small bounded integer range?
- How would you support deleting an old value from a sliding window?
Quick Answer: Design a MedianFinder that supports arbitrary integer insertions and constant-time median queries. Use balanced max and min heaps for the lower and upper halves, with O(log n) insertion and correct averaging for even counts.
Implement run_median_finder(operations) as a portable MedianFinder session. Each [0, value] row inserts one integer and each [1, 0] row queries the current median; return query results in order, using the middle value for odd counts and the arithmetic mean of the two middle values for even counts.
Constraints
- 0 <= operations.length <= 200, and every operation contains exactly two integers.
- Operation kinds are 0 for add and 1 for median; every median query occurs after at least one add.
- Inserted values are between -1,000,000,000 and 1,000,000,000.
Examples
Input: [[0, 5], [1, 0], [0, 15], [1, 0], [0, 1], [1, 0], [0, 3], [1, 0]]
Expected Output: [5.0, 10.0, 5.0, 4.0]
Input: [[0, 1], [0, 2], [1, 0]]
Expected Output: [1.5]
Hints
- Keep the lower half in a max-heap and the upper half in a min-heap.
- After every insertion, preserve value ordering between the heaps and keep their sizes equal or give the lower heap one extra value.