Katkat
Back

Approximate a percentile from buckets

GoogleData Scientist · Technical Screen
MediumData ScientistTechnical ScreenStatistics & Math

Last updated

This question tests the ability to interpolate values within histogram buckets to estimate a specific percentile, requiring an understanding of linear versus log-space assumptions.

Problem Statement

You are given a list of histogram buckets that represent the distribution of latency (in milliseconds) for a service. Each bucket is defined by a (lower_bound, upper_bound) pair and a count representing the number of observations within that interval.

Your task is to implement a function that estimates the p-th percentile (where 0 < p <= 1) of the distribution.

Assumptions

  1. Assume values are uniformly distributed within each bucket.
  2. The buckets cover the entire range of data; there are no observations outside the range defined by the minimum and maximum bounds.
  3. The function signature is: estimate_percentile(buckets, p) where buckets is a list of objects containing lower, upper, and count.

Example

Buckets: [{"lower": 0, "upper": 10, "count": 50}, {"lower": 10, "upper": 50, "count": 50}] Goal: Find the 75th percentile.

  1. Total observations = 100.
  2. Target index = 0.75 * 100 = 75.
  3. The first bucket contains 50 observations. We need 25 more observations (75 - 50 = 25) from the second bucket.
  4. The second bucket has 50 observations over a range of 40 (50 - 10).
  5. Using uniform interpolation: 10 + (25 / 50) * 40 = 30.

Constraints

  • The input buckets is sorted by lower bound.
  • Handle cases where p falls exactly on a bucket boundary.
  • If a bucket has a count of 0, it should not contribute to the percentile calculation.
  • What happens if the final bucket is open-ended (e.g., upper: Infinity)?

Hints

Hint 1

First, calculate the total count of observations to determine the target rank, which is `p * total_count`.

Hint 2

Iterate through the sorted buckets, maintaining a running sum of counts until the target rank falls within the current bucket.

Hint 3

Once the target bucket is identified, use the ratio of the remaining required count to the total bucket count to linearly interpolate between the bucket's lower and upper bounds.

Follow-up questions

  • How would your approach change if the buckets represented logarithmic intervals rather than linear ones?
  • If the buckets were extremely coarse (e.g., only two buckets), why might a uniform distribution assumption lead to significant error?
  • How could you modify the data collection process or storage to provide more accurate quantile estimates without storing every raw data point (e.g., mention T-Digest or KLL sketches)?