Compute the Median After Each Stream Insertion
Company: Amazon
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
# Compute the Median After Each Stream Insertion
Given a stream of integers, return the median after each value is inserted. For an odd number of observed values, the median is the middle value in sorted order. For an even number, it is the arithmetic mean of the two middle values.
## Function Signature
```python
def running_medians(values: list[int]) -> list[float]:
```
## Input
- `values` lists stream arrivals in order.
## Output
Return an array of the same length. Element `i` is the median of `values[0:i+1]` and must be represented as a floating-point number.
## Constraints
- `0 <= len(values) <= 200_000`
- `-10^9 <= values[i] <= 10^9`
- Duplicate values are allowed.
- The input array must not be mutated.
- Compute even-length medians without overflowing a fixed-width integer before conversion.
## Examples
```text
values = [5, 2, 10, 4]
output = [5.0, 3.5, 5.0, 4.5]
```
```text
values = [-1, -1, 8]
output = [-1.0, -1.0, -1.0]
```
```text
values = []
output = []
```
Quick Answer: Compute the median after every insertion into an integer stream without repeatedly sorting the full prefix. Practice maintaining balanced data structures, handling duplicates and negatives, producing even-count averages safely, and meeting large-input time bounds.
