Compute K-th Percentile | Dataford Interview Questions

Pinterest monitors request latency for services such as Pin delivery and home-feed generation. Given an array of server response times and an integer percentile k, return the response-time value at the k-th percentile using the nearest-rank definition.

The nearest rank is ceil(k * n / 100), where n is the number of response times. After sorting the values conceptually, return the value at zero-based index ceil(k * n / 100) - 1. You must not fully sort the array in the primary solution.

Formal Specification

Implement percentile(response_times, k). response_times is a non-empty array of integers representing milliseconds. k is an integer from 1 through 100. Return an integer containing the nearest-rank percentile value. The input array may be modified.

Constraints

1 <= len(response_times) <= 10^5
1 <= response_times[i] <= 10^9
1 <= k <= 100
Duplicate response times are allowed

Function Signature

def percentile(response_times, k):

Your question is Compute K-th Percentile. Start with the requirements in the Question tab.

Run and submit as often as you like. When you're ready, talk me through your approach or go straight to the code.

Problem

Formal Specification

Constraints

1 <= len(response_times) <= 10^5
1 <= response_times[i] <= 10^9
1 <= k <= 100
Duplicate response times are allowed

Function Signature

def percentile(response_times, k):

Your question is Compute K-th Percentile. Start with the requirements in the Question tab.

Run and submit as often as you like. When you're ready, talk me through your approach or go straight to the code.