hardHeap / Priority QueueAI-applied~36 min
Streaming Token Rate Median
An inference server reports tokens-per-second after each request and must surface the running median throughput on a live dashboard. Values arrive one at a time and the median is queried after every insertion.
Problem
Process a stream of integers; after each insertion, report the median of all values seen so far. For an even count, the median is the average of the two middle values. Return the list of medians.
Input
An array stream of length n (1 ≤ n ≤ 10^5), values in [0, 10^6].
Output
An array of n medians (floating point), one after each insertion.
Constraints
- Median queried after every insertion
- Even counts average the two middle elements
- Aim for O(log n) per insertion
Examples
Example 1
Input
stream = [1, 2, 3]
Output
[1.0, 1.5, 2.0]
After 1 → 1.0; after 1,2 → 1.5; after 1,2,3 → 2.0.
Example 2
Input
stream = [5, 5]
Output
[5.0, 5.0]
Duplicate values keep the median at 5.