Loading page…
Practice problem · easy
A monitoring system records the latency of every request in whole milliseconds. No latency is above 1,000 ms, because slower requests are cut off.
To report percentiles, the system needs the latencies of one hour in increasing order. Your team lead asks you to sort them without comparing the values with each other.
Write sort_by_buckets(latencies).
latencies[i] is the latency of the i-th request, a whole number from 0 to 1000.Input: latencies = [5, 3, 5, 0, 3]
Output: [0, 3, 3, 5, 5]The trace keeps one counter for each possible latency, then writes the values out in order.
| Step | What happens | Counters or output |
|---|---|---|
| 1 | Read 5, 3, 5, 0, 3 | 0: 1, 3: 2, 5: 2 |
| 2 | Walk 0 to 1000, write 0 once | 0 |
| 3 | Write 3 twice | 0, 3, 3 |
| 4 | Write 5 twice | 0, 3, 3, 5, 5 |
Counters that are 0 write nothing. The output is [0, 3, 3, 5, 5].
Input: latencies = []
Output: []An empty list gives an empty list.
Input: latencies = [1000, 0]
Output: [0, 1000]Both values are far apart, and the counters between them stay at 0, so the output is [0, 1000].
0 ≤ latencies.length ≤ 100,000 (requests in an hour)0 ≤ latencies[i] ≤ 1,000 (milliseconds)A comparison sort needs about n log n steps, which is about 1.7 million at n = 100,000. That is fast enough, but the value range is tiny. With only 1,001 possible values, one counter per value sorts in n + 1,001 steps with no comparisons at all.
sort_by_buckets · runs in your browserCoding is easiest on a laptop. On a phone, read, trace and try small edits.