Nearest-Rank Latency Percentile
Problem Statement
Compute a latency percentile from a list of samples using the nearest-rank method, the standard for p50/p95/p99 dashboards.
Background
Sort the n samples ascending. The nearest-rank percentile p (in 0..100) is the value at 1-based rank ceil(p/100 * n) (rank at least 1). This returns an actual observed sample, not an interpolated value.
Your Task
def percentile(samples, p):
Return the sample at the nearest rank for percentile p.
Input Format
- samples (non-empty list of numbers), p (number in 0..100).
Output Format
- A number (one of the samples).
Sample
print(percentile([10, 20, 30, 40, 50], 95))
Output:
50
Example:
print(percentile([10, 20, 30, 40, 50], 95))
50
- Sort the input samples in ascending order to establish the rank positions: [10,20,30,40,50], where n=5.
- Calculate the target rank using the nearest-rank formula with p=95: ⌈10095​×5⌉=⌈4.75⌉=5.
- Ensure the rank is at least 1 (it is already 5) and convert this 1-based rank to a 0-based index for retrieval: 5−1=4.
- Retrieve the value at index 4 from the sorted list, which corresponds to the 5th element.
- The final output is 50
Constraints:
- Sort ascending; rank =
ceil(p/100 * n), clamped to at least 1. - Return the value at that 1-based rank.
samplesis non-empty.
1. Background Knowledge
In production ML systems, raw latency data is noisy and unbounded. Engineers rely on percentiles (p50, p95, p99) to summarize tail behavior and define Service Level Objectives (SLOs). Unlike the mean, which is skewed by outliers, the 99th percentile tells you that 99% of requests completed faster than this value. This makes it the standard metric for dashboards and alerting.
There are several ways to compute percentiles, such as linear interpolation (the default in many libraries like NumPy). However, the nearest-rank method is preferred in observability because it guarantees the returned value is an actual observed sample, not a synthesized number. This aligns with the intuition that "95% of my requests were this fast or faster."
The nearest-rank method is defined mathematically. Given n sorted samples and a percentile p (where 0≤p≤100), the rank r is calculated as:
r=⌈100p​×n⌉The result is the value at index r−1 (converting from 1-based to 0-based indexing). If the calculation yields a rank less than 1, it is clamped to 1.
2. Algorithm Approach
This is a straightforward sorting and indexing problem. The approach involves three distinct phases:
- Normalization: Ensure the data is in a comparable order by sorting the input list in ascending order.
- Rank Calculation: Apply the nearest-rank formula to determine the 1-based position of the desired percentile.
- Retrieval: Convert the 1-based rank to a 0-based array index and return the corresponding element.
No complex data structures or iterative searches are required; the problem relies on basic arithmetic and list access.
3. Step-by-Step Strategy
- Sort the Samples: Create a sorted copy of the input list. Do not modify the original list if possible, though for this specific function signature, sorting in-place or using a new list is acceptable.
sorted_samples = sorted(samples)
n = len(sorted_samples)
- Calculate the Raw Rank: Compute 100p​×n. Note that this will likely be a floating-point number.
Continue the full explanation
You're reading the free preview. Unlock the complete walkthrough, the code editor, test runner and reference solution with Premium.
Editor locked
The code editor is locked for Pro problems. It is only available for free problems. Please upgrade to gain access to the code editor for all problems.