Track the Running Median of an Integer Stream
Company: Google
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
## Track the Running Median of an Integer Stream
### Problem
Implement `runningMedianTwice(values) -> mediansTwice`.
Process `values` from left to right. After each insertion, compute the median of the prefix seen so far and append twice that median to the result. This encoding avoids floating-point output:
- For an odd-length prefix, append two times its middle sorted value.
- For an even-length prefix, append the sum of its two middle sorted values.
Return one integer for every input value, in prefix order. The input must not be mutated.
### Constraints
- `0 <= values.length <= 200,000`.
- `-1,000,000,000 <= values[i] <= 1,000,000,000`.
- Use signed 64-bit arithmetic when adding or doubling values.
- Target `O(n log n)` time and `O(n)` auxiliary space.
```hint Trace both prefix parities
Before selecting a data structure, write the expected result after each insertion for a stream with duplicates and with values arriving in descending order.
```
### Examples
```text
values = [5, 2, 8, 1]
mediansTwice = [10, 7, 10, 7]
```
The prefix medians are `5`, `3.5`, `5`, and `3.5`.
```text
values = [-2, -2, 4]
mediansTwice = [-4, -4, -4]
```
### Discussion Requirements
- Explain how two priority queues can maintain the lower and upper portions of the stream and which balance invariant is required.
- If every value lies in a small fixed integer range, compare the heap solution with a frequency table and a maintained order statistic.
- If the query changes from median to an arbitrary rank `k`, explain which structures still work and what additional balancing or order-statistic support is needed.
Overview: Track twice the median after each integer arrives in a stream, avoiding floating-point output for both odd and even prefixes. This coding problem assesses dynamic order statistics, balancing invariants, overflow-safe arithmetic, edge cases, and logarithmic update performance.
Read the full Google Software Engineer interview experience this question came from
You are given a list of integers `values` that arrives as a stream. Process the
values from left to right. After each insertion, look at the prefix seen so far,
sort it, and take its median. Instead of returning that median directly, return
**twice** the median, which is always an exact integer:
- If the prefix has **odd** length, append `2 * m`, where `m` is the single
middle value of the sorted prefix.
- If the prefix has **even** length, append `a + b`, where `a` and `b` are the
two middle values of the sorted prefix.
This doubled encoding is what makes the answer exact: the true median of an
even-length prefix can be a half-integer, but twice that median never is. No
floating point is involved anywhere.
Return the list `mediansTwice`, which contains exactly one integer per input
value, in prefix order. If `values` is empty, return an empty list. The input
list must not be modified.
The answer is fully determined for every input: the result has the same length
as `values`, position `i` depends only on `values[0..i]`, and both the odd and
even rules select from the sorted multiset of that prefix, so duplicates and
ties introduce no ambiguity.
### Example 1
```
Input: values = [5, 2, 8, 1]
Output: [10, 7, 10, 7]
```
The prefixes are `[5]`, `[5, 2]`, `[5, 2, 8]`, `[5, 2, 8, 1]`. Sorted, they are
`[5]`, `[2, 5]`, `[2, 5, 8]`, `[1, 2, 5, 8]`, whose medians are `5`, `3.5`, `5`,
and `3.5`. Doubling each gives `10`, `7`, `10`, `7`. Concretely: the first
prefix is odd, so `2 * 5 = 10`; the second is even, so `2 + 5 = 7`; the third is
odd, so `2 * 5 = 10`; the fourth is even, so `2 + 5 = 7`.
### Example 2
```
Input: values = [-2, -2, 4]
Output: [-4, -4, -4]
```
Sorted prefixes are `[-2]`, `[-2, -2]`, `[-2, -2, 4]`. The first is odd:
`2 * -2 = -4`. The second is even: `-2 + -2 = -4`. The third is odd, and its
middle value is still `-2`: `2 * -2 = -4`. Duplicate values are counted with
multiplicity, exactly as they appear in the stream.
Constraints
- 0 <= values.length <= 200000
- -1000000000 <= values[i] <= 1000000000
- Every returned value satisfies -2000000000 <= mediansTwice[i] <= 2000000000. That exceeds the range of a signed 32-bit integer, so use signed 64-bit arithmetic (Java long, C++ long long) when doubling or summing middle values.
- The returned list has exactly the same length as values; an empty input returns an empty list.
- values must not be mutated by your solution.
- Target O(n log n) time and O(n) auxiliary space, where n = values.length.
Examples
Input: ([],)
Expected Output: []
Input: ([7],)
Expected Output: [14]
Hints
- Write out the answer after each insertion for a short stream by hand. Notice that only the one or two middle elements of the sorted prefix ever matter -- everything else in the prefix is irrelevant to the answer at that step.
- Re-sorting the whole prefix after every insertion is O(n^2 log n) and will not finish on the largest input. You only need the largest element of the smaller half and the smallest element of the larger half after each step. Which container hands you one of those in O(log n) per update?
- Whatever you keep, fix the size relationship between the two halves first -- either equal sizes, or one half exactly one element larger -- and restore it after every insertion before you read the answer. Getting that invariant wrong is what makes odd-length and even-length prefixes disagree.
Community answers
Answer by memo
def runningMedianTwice(nums):
left = [] # max heap
right = [] # min heap
def find_median(num):
heapq.heappush(left, -num)
if len(left) - len(right) <= 1:
if left and right and -left[0] > right[0]:
l1 = -heapq.heappop(left)
r1 = heapq.heappop(right)
heapq.heappush(left, -r1)
heapq.heappush(right, l1)
else:
l1 = -heapq.heappop(left)
heapq.heappush(right, l1)
# return the median
if len(left) - len(right) == 1:
return -left[0]*2
else:
return (-left[0] + right[0])
ans = []
for i, num in enumerate(nums):
med = find_median(num)
ans.append(med)
return ans