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: - `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.