Estimate percentile from buckets

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 `bucket_count_i` is the number of queries whose true `search_count` falls in that bucket. The buckets are non-overlapping and 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 distribution? ### Constraints & Assumptions - You only know bucket boundaries and bucket counts. - A point estimate requires an assumption about the distribution within the selected bucket. - The true percentile is only identifiable up to a bucket interval without such an assumption. - Handle empty buckets, extreme percentiles, coarse buckets, uneven bucket widths, and log-spaced buckets. ### Clarifying Questions to Ask - What percentile definition should be used: nearest rank or interpolated quantile? - Are bucket intervals left-closed and right-open? - Are buckets linearly spaced or log-spaced? - Are `search_count` values continuous or discrete integers? - Should the answer be a point estimate or an uncertainty interval? ### Part 1 - Locate The Percentile Bucket How do you identify the bucket containing the target percentile? #### What This Part Should Cover - Total count, target rank, cumulative counts, and first bucket whose cumulative count reaches the rank. ### Part 2 - Explain Why Midpoint Can Be Poor Why is returning the bucket midpoint often a weak estimate? #### What This Part Should Cover - Midpoint ignores where the target rank lies within the bucket. - Wide, uneven, skewed, log-spaced, or heavy-tailed buckets can make midpoint biased. ### Part 3 - Improve With Interpolation How would you interpolate within the bucket? #### What This Part Should Cover - Fractional position inside the selected bucket. - Linear interpolation under a uniform-within-bucket assumption. - Log-space interpolation when buckets are log-spaced and values are multiplicative. ### Part 4 - Handle Edge Cases And Complexity What edge cases and complexity should be discussed? #### What This Part Should Cover - Empty buckets, percentile 0 or 100, exact boundaries, coarse buckets, discrete counts, and precomputed prefix sums. - `O(K)` scan or `O(log K)` lookup with prefix sums. ### What a Strong Answer Covers - Finds the bucket by cumulative mass. - Uses interpolation while naming the assumption. - States uncertainty when buckets are coarse. - Handles edge cases and avoids false precision. ### Follow-up Questions - What if the selected bucket is very wide? - What if buckets are logarithmic? - How would you estimate confidence intervals? - How would you answer many percentile queries efficiently? - What if the percentile falls in an empty bucket?