Quantile Calculator

An easy Python interview practice problem on DataDriven. Write the Python and run it against test cases, with instant feedback.

Domain
Python
Difficulty
easy
Seniority
L4
Asked in
Netflix

Problem

Our analytics platform reports percentile summaries over batches of metric samples. Given the samples and a percentile from 0 to 100, return the value at that percentile.

Mark the boundary value at a given point.

Example 1

Input:

data = [3,1,4,1,5,9,2,6], percentile = 50

Output:

3.5

Example 2

Input:

data = [10,20,30,40,50], percentile = 25

Output:

20

Worked solution and explanation

The trap beneath the percentile

This is linear interpolation wearing a percentile costume. The real skill: turn the percentile into a fractional rank with percentile / 100 * (n - 1), then blend the floor and ceiling neighbors in proportion to the fractional part. Anyone can sort and index; what separates candidates is the boundary. At percentile 100 the position is exactly n - 1, so a naive upper = lower + 1 reads sorted_data[n] and raises IndexError, crashing on the one case that should return the maximum. Skip the blend and you return 3 instead of 3.5, a value that is not even in the data.

Break down the requirements

Step 1: Sort before you index

Percentiles are defined over ordered values, so sorted(data) comes first. The samples arrive unsorted and may hold duplicates, both legitimate and both must survive the sort.

Step 2: Map the percentile to a fractional position

percentile / 100 * (n - 1) lands somewhere between index 0 (percentile 0, the minimum) and n - 1 (percentile 100, the maximum). Dividing by 100 is easy to forget: the percentile is on a 0-100 scale, not 0-1.

Step 3: Blend the two neighbors, or guard the edge

Take the integer floor lower and the fractional part fraction. When fraction is non-zero, return sorted_data[lower] + fraction * (sorted_data[upper] - sorted_data[lower]). When upper would fall off the end (an exact hit at the top), return sorted_data[lower] instead of indexing past the array.

The solution

Sort, index, and linearly interpolate
def quantile_calculator(data, percentile):
    sorted_data = sorted(data)
    n = len(sorted_data)
    pos = percentile / 100 * (n - 1)
    lower = int(pos)
    upper = lower + 1
    if upper >= n:
        return sorted_data[lower]
    fraction = pos - lower
    result = sorted_data[lower] + fraction * (sorted_data[upper] - sorted_data[lower])
    return result

Common follow-up questions