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 nth 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.