Running Median of a Data Stream

Reported in interviews at Cognitiv Palantir Stackadapt

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_median is only called after at least one add_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.

Related free problems