Running Median of a Data Stream
Problem statement
Integers arrive one at a time from a stream. Design a class that can add a number and report the median of all numbers seen so far at any moment. The median is the middle value when the count is odd and the mean of the two middle values when it is even.
class MedianFinder:
def add_num(self, x: int) -> None: ...
def find_median(self) -> float: ...
Aim for $O(\log n)$ per add_num and $O(1)$ per find_median, where $n$ is the number of values added so far. The judge replays a list of operations on one fresh object through a wrapper provided in the editor and collects one result per operation (None for adds, the median as a float otherwise).
Constraints
- $1 \le$ number of operations $\le 5 \times 10^4$
- $-10^5 \le x \le 10^5$
find_medianis only called after at least oneadd_num
Examples
Example 1: add 5, median, add 1, median, add 9, median, add 3, median returns None, 5.0, None, 3.0, None, 5.0, None, 4.0 (sorted values: [5], [1, 5], [1, 5, 9], [1, 3, 5, 9]).
Example 2: add 1, add 2, median, add 3, median returns None, None, 1.5, None, 2.0.
Show hint
To report the middle value, which elements of the data do you actually need to see quickly, and does everything else need to be in order?
Relevant roles: ML Engineer, Forward Deployed Engineer and AI Engineer.