Maintain the Median of a Data Stream
Company: Xiaopeng
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
# Maintain the Median of a Data Stream
Process a stream of integers and return the median after every insertion. For an odd number of values, the median is the middle value. For an even number, return the arithmetic mean of the two middle values. Return each median as a floating-point number.
## Function Contract
Implement `running_medians(values) -> list[float]`.
## Constraints
- 0 <= number of values <= 200000.
- Each value is an integer between -10^9 and 10^9.
- Duplicates and negative values are allowed.
- The result after each insertion must reflect all values seen so far.
## Examples
```text
values = [5, 2, 10, 4]
output = [5.0, 3.5, 5.0, 4.5]
```
```text
values = []
output = []
```
```hint Exercise median boundaries
Test odd and even prefix lengths, duplicates, negative values, and a large gap between the two middle values.
```
```hint Plan for the stream size
Explain how each insertion and median query can meet the input limit without sorting every prefix from scratch.
```
Quick Answer: Process a stream of integers and return the median after every insertion. Work through the function contract, boundary cases, correctness argument, and time and space complexity expected in a production-quality solution.
Process integer `values` in order and return the median after every insertion. Odd prefixes use their middle value; even prefixes use the arithmetic mean of the two middle values. Return every result as a floating-point number.
Constraints
- 0 <= len(values) <= 200000.
- Each value is an integer from -10^9 through 10^9; duplicates and negatives are allowed.
- Return one floating-point median for every input prefix in the same order.
Examples
Input: ([],)
Expected Output: []
Explanation: Empty input returns no medians.
Input: ([5],)
Expected Output: [5.0]
Explanation: A singleton stream has median five.
Hints
- Test empty and singleton streams plus both odd and even prefix lengths.
- Include duplicates, negative values, and both numeric limits.
- Use ascending, descending, and alternating low/high insertion orders.