Median of a Stream I
Numbers arrive one at a time. Implement ExactStreamingMedian: add(x) takes the next number; median() returns the median of everything added so far — the mean of the two middle values for an even count — or null before anything is added.
m = ExactStreamingMedian() m.add(1); m.add(2); m.add(3) m.median() -> 2 m.add(4) m.median() -> 2.5
Both operations should beat re-sorting: O(log n) per add, O(1) per median.
Hints
Hint 1
A max-heap for the lower half and a min-heap for the upper half, rebalanced so the lower half is the same size or one larger.
Hint 2
The median is the lower heap's top when the count is odd, otherwise the mean of both tops.