Streaming Order Statistics

Learning outcomes

Trade Republic’s documented coding prompt asks for a data structure that supports adding a quote (symbol, price, timestamp) and retrieving the median price for a symbol within the last hour. The median is an order statistic, the value at the middle rank of a sorted collection, and the challenge is to answer it on a stream that never ends and within a window that constantly expires. This concept derives the two-heap median structure from first principles, shows where it breaks when the window starts expiring values, and extends the same intuition to percentiles and to the approximate sketches a production system actually ships.

After studying this page, you can:

• Derive the two-heap (max-heap lower half, min-heap upper half) median structure and its rebalancing invariant.
• Justify the logarithmic insert and constant median retrieval complexity against the naive sorted-list baseline.
• Explain why a sliding time window breaks the plain two-heap and how lazy eviction repairs it.
• Compare lazy eviction against indexed structures (order-statistics trees, indexed heaps) and pick by workload.
• Generalize from median to arbitrary percentiles and reason about P99 latency.
• Argue when to replace exact order statistics with t-digest or HDR histograms at production scale.

The prompt and the median problem

The exact prompt is: implement a data structure supporting add quote (symbol, price, timestamp) and retrieve the median price for a symbol within the last hour. There is one such structure per symbol, because medians do not combine across symbols. Per symbol, the operations are: insert a price tagged with a timestamp, evict every price older than one hour, and return the median of the survivors. The natural reading is a time window keyed by symbol.

For an odd number of live prices the median is the middle element in sorted order. For an even number it is the mean of the two middle elements. Both definitions reduce to knowing the elements at the middle ranks.

The median is the middle element for odd n and the mean of the two middle elements for even n, where x-subscript-k denotes the kth element in sorted order.

A median is more robust than a mean when the data is skewed, and price data is skewed constantly. One anomalous print at a wildly off price drags the mean somewhere meaningless while the median sits unmoved at the value most trades actually touched. That robustness is why a trader watching quote activity wants the median price of the last hour, not the average. It tells them where the center of mass of real trading sits, ignoring a stray fat-finger print.

The hard part of a median, unlike a mean, is that it is positional. The mean is a sum divided by a count, and a running sum updates in constant time. The median is the value at rank n over 2 in sorted order, and there is no closed-form running update for a rank. To answer it you must either keep the data sorted, or keep a structure that knows the rank of every element cheaply. That single difference, sum-based versus rank-based, is what makes streaming order statistics a distinct family of problems from streaming averages.

Why sorting on every query fails

The baseline solution stores every live price in an array, sorts it on every median query, and reads the middle. It is correct and trivial, and its cost is the problem.

Per-query cost of the resort-on-query baseline, superlinear in the live set size n.

If the system answers the median on every quote and the live set holds thousands of prices, every query sorts thousands of elements. Inserting in sorted position and reading the middle in constant time trades one cost for another: insert becomes logarithmic to find the position plus linear to shift the array. A balanced search tree gives logarithmic insert and logarithmic median, which is better, but still not the best attainable. The two-heap structure does better than a tree for the median specifically, because it exploits the fact that we only ever need the middle, never an arbitrary rank.

The two-heap split

The aha reframe is to split the sorted live set into two halves and hold each half in a heap that exposes its boundary. The lower half lives in a max-heap, so its root is the largest of the small values, which is exactly the left middle element. The upper half lives in a min-heap, so its root is the smallest of the large values, which is exactly the right middle element. The median is then a function of the two roots, read in constant time, with no traversal.

The invariant that makes this work is a size balance rule. The two heaps may differ in size by at most one. When they are equal in size, the median is the average of the two roots. When one is larger, that larger heap’s root is the median. Without the balance rule a new element could pile into one side and the roots would no longer be the middle ranks.

The balance invariant keeps the two roots at the middle ranks, so the median is read off the roots with no traversal.

The per-operation cost is logarithmic for insert, because each new value pushes one heap and possibly moves one element across, and constant for median retrieval.

Each insert pushes one heap at logarithmic cost and rebalances if needed; median retrieval is constant time from the roots.

Insert and rebalance step by step

The insert algorithm keeps the invariant by deciding which half the new value belongs to, pushing it there, and rebalancing if the size difference exceeds one. Deciding which half means comparing the new value to the lower root: if it is less than or equal to the largest of the lower half, it belongs in the lower half, otherwise in the upper. After the push, if one heap has two more elements than the other, move the root of the larger heap to the smaller one. That single move restores the balance invariant.

The rebalance step is the heart of the structure. Moving one root across is enough because a single insert changes the size balance by at most one, so the imbalance never exceeds two before rebalancing fixes it. This is why the median specifically gets this fast structure, while an arbitrary rank would not: we only ever need the middle, and the middle always sits at a root.

The two-heap structure exploits that only the middle is ever asked for

A balanced search tree answers any rank in logarithmic time. The two-heap median answers only the middle rank, but does it in constant time, because the middle is always at a root. The structure trades rank flexibility for median speed, which is the right trade when median is all you ever need.

The time-window expiry complication

The plain two-heap structure handles an unbounded stream with no expiry, which is not what the prompt asks. The prompt wants the median within the last hour, so values must leave the structure as they age out, and the median must stay correct after they leave.

This is where the textbook structure breaks. A binary heap has no efficient arbitrary deletion. Removing a value that is not the root means finding it in the heap, deleting it, and restoring the heap property, which is linear in the worst case unless you keep an auxiliary index. Worse, the values to expire are chosen by timestamp, not by rank, so the structure has no cheap way to know which heap a soon-to-expire value lives in, let alone where in that heap.

Plain heaps delete the root in logarithmic time but an arbitrary element in linear time, so expiry by timestamp is expensive.

The two standard repairs are lazy eviction and indexed structures. Each trades something different.

Lazy eviction versus indexed structures

Lazy eviction accepts that the heap contains stale values and refuses to delete them eagerly. Instead it records every insert with its timestamp in an auxiliary queue ordered by arrival. On every median query, it first pops from the front of that queue every value whose timestamp is older than the window cutoff. For each popped value it marks it as logically deleted in a tombstone map keyed by value (or by a unique insert id). Then, when it reads the roots to compute the median, it checks whether each root is tombstoned, and if so pops it and checks the next, until both roots are live. The tombstoned values are removed from the heap lazily, only when they bubble up to a root.

The amortized cost stays logarithmic per insert and constant per median read, because each value is inserted once, tombstoned once, and physically popped at most once. The catch is that the heap can hold many tombstoned values that have not yet risen to a root, so memory is larger than the live set, and in the worst case the heap holds every expired value until it happens to surface. A periodic compaction that rebuilds both heaps from the live set bounds the memory bloat.

The indexed alternative pays the cost up front to keep expiry logarithmic. An indexed heap (a heap with a position map from value to its slot) supports arbitrary deletion in logarithmic time: swap the value with the last element, remove the tail, and sift the swapped element up or down to restore the heap, updating the position map at each swap. The structure is more complex and the constant factors are larger, but expiry is bounded logarithmic rather than amortized. An order-statistics tree (a balanced tree augmented with subtree sizes) does the same job and answers any rank in logarithmic time, at the cost of even larger constants and more code.

The choice between lazy eviction and an indexed structure is a workload decision. Lazy eviction wins when median queries are frequent relative to expiries and the heap bloat is tolerable, because its code is short and its common path is fast. An indexed structure wins when expiries are frequent, when memory is tight, or when the workload needs arbitrary percentiles, not just the median, in which case the order-statistics tree is the more general tool.

Indexed structures support arbitrary percentiles and logarithmic expiry while lazy eviction keeps the median fast and the code simple, making the choice a workload tradeoff.

Code for lazy eviction with tombstones

The lazy-eviction design wraps the plain MedianHeap with an arrival queue and a tombstone set. Each insert records the value and its timestamp in the queue. Each median call first flushes expired timestamps from the queue head, adding their values to the tombstone set, then reads the median while clearing tombstoned roots from the heaps.

The lazy-eviction pattern is the same insight as the separate-chaining approach in the sliding window: delay expensive work until it is forced, and amortize it across operations. A periodic compaction (rebuilding both heaps from the non-tombstoned live set) bounds the memory bloat that would otherwise grow without bound as expired values accumulate in the heaps.

From median to percentiles and P99

The median is the fiftieth percentile. A latency monitoring system wants the ninety-ninth percentile, the value below which ninety-nine percent of observations fall, because that is where the slow tail lives and where customer pain concentrates. The same rank-based definition generalizes the median to any percentile p.

The pth percentile is the element at rank p times n over 100 in sorted order, which generalizes the median (p equals 50).

The two-heap structure does not extend cleanly to arbitrary percentiles, because it is hardwired to the middle rank. The order-statistics tree does, because it tracks subtree sizes and answers any rank in logarithmic time, so P99 is one rank lookup. That is the practical reason to reach for the tree when the workload mentions percentiles rather than median.

The latency-monitoring use case also changes the failure mode that matters. For a single slow query the median is unaffected, which is exactly why the median is the wrong summary for tail latency. P99 exists precisely to surface the tail, and a system that reports only median latency hides the worst customer experience. The engineering lesson is to match the statistic to the question: median for typical behavior, high percentiles for tail behavior.

P99 in a production system also changes the data structure requirement from correctness to bounded error. The exact P99 is the 99th-ranked value in sorted order, which requires the full sorted dataset. At high throughput the memory of holding every observation for P99 is prohibitive, so production systems accept a small error in exchange for sublinear memory, which is where approximate sketches enter.

Approximate order statistics at scale

At production scale the exact structures stop fitting. A symbol that receives thousands of quotes per second accumulates millions of values per hour, and an exact structure holding every value is memory and CPU expensive for a number that only needs to be approximately right. Real systems replace exact order statistics with approximate sketches that use sublinear memory.

The two sketches that dominate practice are t-digest and HDR histograms. A t-digest represents the distribution as a small number of weighted centroids, clustered tightly at the extremes and coarsely in the middle, which gives it very high accuracy at the tails (where P99 lives) and acceptable accuracy at the median. It merges across symbols and across windows, which an exact structure cannot, so it composes horizontally when many shards each see part of the traffic. An HDR histogram buckets values logarithmically across a fixed range and counts per bucket, giving bounded relative error and fast merges at the cost of precommitting to a value range.

A t-digest uses sublinear memory, far smaller than the live set, and merges across shards, which exact structures cannot do.

The senior answer is to use exact order statistics for small or correctness-critical windows (a median price for a single liquid symbol over a minute) and approximate sketches for large, shardable, or tail-focused workloads (P99 latency across a fleet). The prompt’s last-hour median is on the boundary: exact is feasible for a single symbol, approximate becomes attractive when the question scales to many symbols or to a percentile near the tail.

Mergeability is the production payoff

Exact structures do not merge. You cannot take the median of two halves of a dataset from the medians of each half. Sketches like t-digest merge cleanly, which is why a distributed system monitoring P99 across many shards uses them: each shard keeps a small digest, and a global P99 is one merge away.

Common mistakes candidates make

The first mistake is jumping to the two-heap structure without deriving it. The interviewer wants to see the candidate notice that the median is rank-based, that sorting fails, and that the two-heap split keeps the middle at the roots. Arriving at the structure by rote skips the reasoning the round is grading.

The second mistake is forgetting the balance invariant. A two-heap structure without rebalancing drifts, the roots stop being the middle ranks, and the median is silently wrong. The size-may-differ-by-at-most-one rule is the whole correctness argument.

The third mistake is ignoring expiry. The prompt is a time window, not an unbounded stream, and a plain two-heap has no efficient way to forget values. Without lazy eviction or an indexed structure the answer is incomplete.

The fourth mistake is claiming the two-heap extends to P99. It does not. It is hardwired to the middle. Arbitrary percentiles need an order-statistics tree or an approximate sketch, and saying so is part of the answer.

The fifth mistake is ignoring memory at scale. An exact structure holding every quote for an hour at high arrival rate is large, and for a latency percentile across a fleet it is infeasible. Naming the sketch alternative (t-digest, HDR) signals the production mindset.

The sixth mistake is not handling the even-case median formula. For an even number of live values, the median is the average of the two middle values, not just one of them. A candidate who writes the code to return only the lower root has a subtle correctness bug that surfaces only when the live set count flips from odd to even.

What the interviewer asks next

The first follow-up asks how the structure handles expiry. The expected answer names lazy eviction with tombstones for the simple case, or an indexed heap or order-statistics tree for bounded logarithmic deletion, and argues the tradeoff.

The second follow-up asks for a percentile, not the median. The expected answer is that the two-heap does not generalize, and the order-statistics tree (augmented with subtree sizes) answers any rank in logarithmic time.

The third follow-up probes scale. The interviewer asks how the structure behaves across many symbols or many shards. The expected answer is that exact structures do not merge, so a distributed P99 needs a mergeable sketch like t-digest or HDR.

The fourth follow-up probes correctness under duplicate or out-of-order timestamps. The expected answer is that duplicates are handled by the comparison on insert, and out-of-order arrival breaks a strict time-window eviction, requiring a watermark or a buffered sort before insertion.

The final probe asks the candidate to defend the choice between exact and approximate for the last-hour median. The expected answer is that exact is feasible and preferable for a single liquid symbol, because the median is money-adjacent and correctness matters, but approximate becomes attractive when the workload scales to many symbols or moves to tail percentiles where mergeability matters.

Mastery Questions

Question

Why does the streaming median resist the running-sums trick that solves streaming VWAP?

Question

Explain the two-heap median structure and the invariant that makes it correct.

Question

What is the per-operation complexity of the two-heap median, and why does each insert cost logarithmic?

Question

Why does a sliding time window break the plain two-heap, and what are the two standard repairs?

Question

How do you compute the 99th percentile, and why does the two-heap not extend to it?

Question

Why are approximate sketches like t-digest used in production instead of exact structures?

Question

How would you defend exact versus approximate for the last-hour median of one liquid symbol?

Answer

A mean is a sum divided by a count, and a running sum updates in constant time. A median is the value at the middle rank in sorted order, a positional quantity with no closed-form running update. To answer it cheaply you must either keep the data sorted or hold a structure that tracks ranks, which is a different family of problem from sum-based averages.

Answer

Hold the lower half in a max-heap and the upper half in a min-heap. The max-heap root is the largest of the small values (the left middle) and the min-heap root is the smallest of the large values (the right middle), so the median reads off the two roots in $O(1)$. The invariant is that the heap sizes differ by at most one: equal sizes mean the median is the average of the roots, a one-off imbalance means the larger heap's root is the median. Rebalance after each insert by moving one root across if the sizes differ by two.

Answer

Insert is $O(\log n)$, median retrieval is $O(1)$, space is $O(n)$. Each insert pushes one value into one heap (a logarithmic heap push), and the rebalance moves at most one root across (another logarithmic push plus a logarithmic poll). Median retrieval touches only the roots, so it is constant.

Answer

A plain binary heap deletes its root in $O(\log n)$ but an arbitrary element in $O(n)$, and the window must evict by timestamp, which picks arbitrary elements. Repair one is lazy eviction: tombstone expired values on query and physically remove them only when they bubble to a root, compacting periodically to bound bloat. Repair two is an indexed heap or order-statistics tree that supports arbitrary deletion in $O(\log n)$ via a position map or subtree sizes.

Answer

The pth percentile is the element at rank $\lceil p \cdot n / 100 \rceil$ in sorted order, so $P_{99}$ is near the top rank. The two-heap is hardwired to the middle rank, its roots are always the two middle values, so it cannot answer an arbitrary rank. The general tool is an order-statistics tree, a balanced tree augmented with subtree sizes, which answers any rank in $O(\log n)$. At scale, replace it with a mergeable sketch like t-digest or HDR.

Answer

Exact structures use $O(n)$ memory, do not merge across shards (you cannot derive the median of a whole from the medians of halves), and become infeasible at millions of values or across a fleet. A t-digest uses $O(k)$ memory with $k$ much smaller than $n$, clusters accuracy at the tails where $P_{99}$ lives, and merges cleanly across shards, so a global percentile is one merge. The trade is approximate answers, acceptable for monitoring and analytics, not for a single money-facing price.

Answer

Exact wins for one liquid symbol over an hour because the live set is bounded and the median feeds a price the customer sees, where correctness matters. The two-heap with lazy eviction is short, fast, and exact. Approximate wins when the workload scales to many symbols or moves to tail percentiles across shards, where mergeability and memory dominate and small relative error is acceptable.

Question

Why does the streaming median resist the running-sums trick that solves streaming VWAP?

Answer

A mean is a sum divided by a count, and a running sum updates in constant time. A median is the value at the middle rank in sorted order, a positional quantity with no closed-form running update. To answer it cheaply you must either keep the data sorted or hold a structure that tracks ranks, which is a different family of problem from sum-based averages.

Prev1 / 7Next