# Design a Streaming Percentile Estimator The source reports a percentile-estimation discussion that escalated to a plus-or-minus error guarantee and a t-digest derivation. The exact comparison with a deterministic rank summary below is practice framing for that reported topic. You receive an unbounded stream of numeric observations and must answer percentile queries without retaining every value. Design an estimator for quantile `q` and explain precisely what an error statement of plus or minus `epsilon` guarantees. Address two targets: 1. a deterministic single-stream summary whose returned value has rank within `epsilon * N` of the target rank after `N` observations; and 2. a centroid-based estimator such as a t-digest that prioritizes accuracy near the tails. Compare update cost, memory, behavior on duplicates and skew, practical merge behavior, and the strength of the guarantees each can honestly claim. Do not assume that the classic deterministic summary can be merged by concatenating or recompressing summaries while retaining its original bound. Do not present empirical t-digest accuracy as a universal worst-case guarantee. ### Constraints & Assumptions - Values arrive one at a time and may be repeated or highly skewed. - Queries occur only after at least one observation. - `0 <= q <= 1` and `0 < epsilon < 1`. - Exact minimum and maximum should be available for `q=0` and `q=1`. - Rank error alone gives no numeric-value error bound without distribution assumptions. - If distributed merging is proposed, state exactly which guarantee survives and under which invariant; otherwise identify the limitation. ### Clarifying Questions to Ask - Is the requested error in rank, relative rank, or numeric value? - Must the bound be deterministic, or is a high-probability or empirical target acceptable? - Which percentiles matter most? - Must independently produced summaries merge without raw observations? ### What a Strong Answer Covers - A precise target-rank convention and testable error definition. - A valid deterministic summary invariant and query argument for one stream. - Honest merge limitations rather than an unsupported guarantee. - A clear t-digest centroid/scale explanation and empirical validation plan. - Edge cases, complexity, duplicates, skew, and adversarial order. ### Follow-up Questions 1. What exact fallback would preserve correctness across workers? 2. How would sliding-window expiration change the design? 3. How would insertion order and merge-tree shape affect validation? 4. How would you measure tail error without storing the production stream indefinitely?