Syllabus Lesson 129 of 141 · Beat your Ghost
Beat your Ghost

No sort: the latency report

Why it matters "Sort it first" turns many problems into easy ones, so it becomes automatic. Some data is shaped so that sorting is the long way round.

A service records how long each request took, in whole milliseconds. Requests time out at 10 seconds, so every value is between 0 and 10,000. Every minute, a job turns about 20,000 values into the numbers on the on-call dashboard: the median, the 90th and 99th percentiles, and the worst.

Nearest-rank percentile: the p-th percentile is the smallest value such that at least p% of all values are at or below it. With 20 values, the 90th percentile is the 18th smallest.

The data

values = [120, 85, 3000, 95, 110, 90, 100, 105, 80, 130]
# latency_report(values) -> {"p50": 100, "p90": 130, "p99": 3000, "max": 3000}

In this problem sorting is banned, by hand or by library. Look at what you know about the values.

Your turn

Write latency_report(values). values is a non-empty list of whole numbers from 0 to 10,000 (about 20,000 of them). Return {"p50", "p90", "p99", "max"}: the nearest-rank 50th, 90th and 99th percentiles (the smallest value with at least p% of the values at or below it) and the largest value. Do not change the list. Rule: no sorting: no sorted(), .sort(), bisect.insort, and no heapq or statistics imports (they sort for you).

Spotted a problem in this lesson? Report it · Ask about this lesson

This exercise opens soon

Finish the lesson before it and this one unlocks. The whole course is free, no account needed, and you can read this lesson right now.

Start at lesson 1 Back to syllabus