Estimate percentile from buckets
Company: Google
Role: Data Scientist
Category: Statistics & Math
Difficulty: medium
Interview Round: Technical Screen
You are given an approximate histogram of search-query frequencies. Each bucket `i` is represented as `(left_bd_i, right_bd_i, bucket_count_i)`, where:
- `left_bd_i` and `right_bd_i` are the lower and upper boundaries of the bucket,
- `bucket_count_i` is the number of queries whose true `search_count` falls in that bucket.
Assume there are `K` non-overlapping buckets sorted by boundary, and you do not have access to the raw per-query `search_count` values.
How would you estimate the `n`th percentile of the underlying `search_count` distribution?
Your answer should address:
1. How to identify which bucket contains the desired percentile.
2. Why simply returning the midpoint of that bucket can be a poor estimate.
3. How to improve the estimate using interpolation within the bucket.
4. What assumptions are required for that interpolation to be reasonable.
5. How to handle edge cases such as empty buckets, percentiles near 0 or 100, and coarse or uneven bucket widths.
Quick Answer: This question evaluates statistical estimation skills, understanding of histogram-based quantile approximation, and the ability to reason about aggregated data distributions and interpolation under limited information.