Loadingone moment…
Sign in to run and submit your work
Reading is open to everyone. Running code and saving drafts need an account so your work is yours and comes back on your next visit.
or
CODE WORKSPACE
A dashboard shows the median latency of a service, updated after every request. The average is dragged around by a few slow outliers; the median is the number half of the requests were faster than. The stream never ends, so re-sorting every reading ever seen each time a new one arrives is not an option.
Write running_median(latencies). It takes latencies, a list of numbers in the order they arrived. It returns a list with the same length. Element i is the median of the first i + 1 readings.
Function to write
running_median(latencies: list[float]) -> list[float]A list with one median per input reading, in input order; averages for even counts are floats.
How to approach it
Keep the smaller half in one heap and the larger half in another, and keep their sizes within one of each other. The median is then at the top of one heap or the average of both tops.
Sample cases
+ 3 held back until you submit
a short stream
Medians after each reading: 5, then 10.0 (average of 5 and 15), then 5, then 4.0 (average of 3 and 5).
Input
Argument 1
[
5,
15,
1,
3
]Returns
[
5,
10,
5,
4
]already sorted readings
Every new value belongs in the upper half; the halves still have to rebalance by size.
Input
Argument 1
[
1,
2,
3,
4,
5
]Returns
[
1,
1.5,
2,
2.5,
3
]falling readings
Every new value belongs in the lower half, the opposite pressure on the same two heaps.
Input
Argument 1
[
9,
7,
5,
3,
1
]Returns
[
9,
8,
7,
6,
5
]no readings yet
Nothing has been measured, so there are no medians to report.
Input
Argument 1
[] (empty list)
Returns
[] (empty list)
Constraints
(a + b) / 2, which is a float.sort on the full history each time.Worked example
Take the readings 5, 15, 1, 3. After 5 the median is 5. After 15 the sorted history is 5, 15, so the median is (5 + 15) / 2 = 10.0. After 1 the sorted history is 1, 5, 15, so the median is 5. After 3 it is 1, 3, 5, 15, so the median is (3 + 5) / 2 = 4.0. The answer is [5, 10.0, 5, 4.0].
The trap: for an even count, seen[len(seen) // 2] and seen[(len(seen) - 1) // 2] return one of the middle values, not their average. The dashboard then shows 5 where it should show 10.0.
What this tests
The two-heap pattern, LeetCode 'Find Median from Data Stream'. A max-heap holds the smaller half and a min-heap holds the larger half, so the median is always at one or both tops. heapq only has a min-heap, so the lower half is stored negated. Data engineers meet this in streaming percentiles and SLO dashboards, where re-sorting all the history on every reading does not scale.
running_median(latencies: list[float]) -> list[float]Submit for review to find out what your query gets right, what it gets wrong, and how it compares with the best working query for this exercise.
This scenario runs a full workspace — editor, canvas and results side by side. It needs a laptop or desktop to be usable. Open this page on a bigger screen to start building.