Streaming Median Tracker
Company: Trexquant
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
# Streaming Median Tracker
Design a data structure that ingests integers one at a time from a stream and can report the **median of every integer inserted so far** at any moment.
The median of a collection of numbers is the middle value once the numbers are arranged in non-decreasing order:
- If the collection has an **odd** number of elements, the median is the single middle element.
- If the collection has an **even** number of elements, the median is the **average of the two middle elements**.
Implement a class `MedianTracker` with the following operations:
- `MedianTracker()` — initialize an empty tracker.
- `add(num)` — insert the integer `num` into the structure. Duplicates and negative values are allowed.
- `median()` — return the median of all integers inserted so far as a floating-point number. This method is only invoked after at least one call to `add`.
### Example
```
MedianTracker t
t.add(1) // multiset = [1]
t.median() // returns 1.0
t.add(3) // multiset = [1, 3]
t.median() // returns 2.0 (average of the two middle values 1 and 3)
t.add(2) // multiset = [1, 2, 3]
t.median() // returns 2.0 (single middle value)
t.add(10) // multiset = [1, 2, 3, 10]
t.median() // returns 2.5 (average of 2 and 3)
```
### Constraints
- Values passed to `add` are 32-bit signed integers; they may be negative and may repeat.
- `add` can be called up to $10^5$ times, interleaved arbitrarily with `median` calls. A solution that re-sorts the data on every `median` call (overall $O(n^2 \log n)$) is too slow — aim for roughly $O(\log n)$ per `add` and $O(1)$ per `median`.
- `median` is never called before the first `add`.
- The returned median must be exact: when the count is even, return the true average of the two middle elements (which may be a non-integer such as `2.5`).
### Required Output
Each call to `median()` returns a single floating-point number equal to the median of all integers inserted up to that point.
Quick Answer: This question evaluates a candidate's ability to design a data structure that maintains a running median over a stream of numbers, testing knowledge of heaps and balanced data partitioning. It is a classic coding and algorithms interview problem used to assess understanding of amortized time complexity and efficient online statistics tracking, requiring practical implementation rather than just conceptual discussion.
Design a data structure that ingests integers one at a time and can report the median of everything inserted so far at any moment.
Because the online judge drives a class through a scripted sequence of calls, implement a single driver function `solution(operations, values)`:
- `operations` is a list of method names. The first is always `"MedianTracker"` (construct/reset an empty tracker). The rest are `"add"` or `"median"`.
- `values` is a parallel list of argument lists. For an `"add"` op the entry is `[num]`; for `"MedianTracker"` and `"median"` it is `[]`.
- For each `"median"` op, compute the median of every integer inserted so far and append it (as a float) to a results list. Return that results list.
Median rules: sort the values inserted so far in non-decreasing order. If the count is odd, the median is the single middle value; if even, it is the average of the two middle values (which may be a non-integer such as `2.5`). Duplicates and negative values are allowed, and `median` is never invoked before the first `add`.
Example: operations `["MedianTracker", "add", "median", "add", "median", "add", "median", "add", "median"]` with values `[[], [1], [], [3], [], [2], [], [10], []]` returns `[1.0, 2.0, 2.0, 2.5]`.
Aim for about O(log n) per add and O(1) per median; re-sorting on every median call is too slow for up to 10^5 operations.
Constraints
- The first operation is always "MedianTracker"; every subsequent op is "add" or "median".
- Values passed to add are 32-bit signed integers; they may be negative and may repeat.
- add can be called up to 10^5 times, interleaved arbitrarily with median calls.
- median is never called before the first add.
- When the running count is even, return the exact average of the two middle elements (may be non-integer, e.g. 2.5).
Examples
Input: (["MedianTracker", "add", "median", "add", "median", "add", "median", "add", "median"], [[], [1], [], [3], [], [2], [], [10], []])
Expected Output: [1.0, 2.0, 2.0, 2.5]
Explanation: Running medians after each add: [1]->1.0, [1,3]->avg(1,3)=2.0, [1,2,3]->2.0, [1,2,3,10]->avg(2,3)=2.5. Matches the prompt example.
Input: (["MedianTracker", "add", "median"], [[], [5], []])
Expected Output: [5.0]
Explanation: Single element: the median is that element as a float.
Hints
- Keep the values split into two halves: a max-heap holding the smaller half and a min-heap holding the larger half. Maintain the invariant that the max-heap has the same size as the min-heap, or exactly one more element.
- Python's heapq is a min-heap; simulate a max-heap by pushing negated values.
- On each add, push then rebalance so |len(small) - len(large)| <= 1. The median is the top of the larger heap when sizes differ, otherwise the average of the two tops.
- Return a float even when the median is a whole number (e.g. 1.0), and use true division so even counts can yield values like 2.5.