Streaming Approximate Quantiles with Rank-Error Guarantees

Reported in interviews at Barclays Citadel Jane Street Two Sigma Exa

Problem statement

You have a stream of $n$ elements arriving one at a time, and you need to answer quantile queries on the fly. For any queried rank fraction $\phi \in (0,1)$, you want to return an element whose rank is within $\pm \varepsilon n$ of the true $\phi$-quantile, where $\varepsilon > 0$ is a precision parameter you choose up front.

Design a one-pass, deterministic streaming algorithm that:

  1. Answers any $\phi$-quantile query with rank error at most $\varepsilon n$.
  2. Uses $O\bigl(\frac{1}{\varepsilon} \log(\varepsilon n)\bigr)$ space.
  3. Processes each incoming element in $O\bigl(\log(1/\varepsilon)\bigr)$ amortized time.

Specifically:

  1. Describe the data structure you maintain and how it is updated when a new element arrives.
  2. Prove that the rank error of any query is at most $\varepsilon n$.
  3. Explain how summaries from two independent streams can be merged while preserving the $\varepsilon$-approximate guarantee -- i.e., why is this structure "mergeable"?

Graded function: an approximate sketch has many acceptable answers, so the grader checks the exact quantity GK approximates. Implement stream_quantiles(stream, phis): for each $\phi$ in phis, return the element of rank $r = \lceil \phi n \rceil$ (1-indexed) in the sorted order of the full stream, with answers in query order. stream is non-empty and each $\phi \in (0, 1)$.

Examples

stream_quantiles([1, 1, 1, 1], [0.25, 0.75]) -> [1, 1]
stream_quantiles([5, 1, 4, 2, 3], [0.2, 0.5, 0.9]) -> [1, 3, 5]

In the second example the sorted stream is $[1, 2, 3, 4, 5]$ and the ranks are $\lceil 1 \rceil = 1$, $\lceil 2.5 \rceil = 3$ and $\lceil 4.5 \rceil = 5$.

Show hint

Instead of storing every value, what if each kept value carried a lower and an upper bound on its rank?

Relevant roles: ML Engineer, Data Scientist, MLOps Engineer and Applied Scientist.

Related free problems