Sliding Window Algorithms at High Throughput

Learning outcomes

Trade Republic’s documented coding screen asks you to compute VWAP (volume-weighted average price) over a sliding window of the most recent trades, under memory and throughput constraints. The interesting part of this prompt is not the VWAP formula, it is the engineering judgment the window adds: how to keep the answer up to date on every new trade without rescanning the whole window, how to bound memory when trades never stop arriving, and how to reason about numeric stability when you are summing millions of large values. This concept derives the sliding window from a naive first attempt up to a ring-buffer design that runs at throughput.

After studying this page, you can:

• Derive the running-numerator and running-denominator trick that makes a count-window VWAP an amortized constant operation per trade.
• Distinguish a count window (last N trades) from a time window (last K seconds) and explain why the data structure differs.
• Implement the count window with a ring buffer and the time window with a head-evicting deque.
• Justify memory bounds under unbounded arrival rates and state the overflow hazard.
• Explain why naive floating point summation drifts and apply Kahan or fixed-point summation.
• Argue what changes when the arrival rate reaches millions of trades per second.

The interview prompt, restated

The exact prompt from the interview source is: given a stream of stock trades (timestamp, price), design an algorithm to efficiently calculate VWAP over a sliding window of the last N trades, consider memory constraints and high throughput. Read it as four simultaneous demands: an efficient update per trade, a sliding bound on what counts, bounded memory, and graceful behavior under high arrival rate. The trap is to solve only the first and assume the rest follow. A senior candidate names all four before writing code, and the design they produce is the one that satisfies all four at once.

VWAP is the volume-weighted mean of price over the window. For trades with prices and volumes, the formula divides the total money that moved by the total volume that moved.

Total money that moved divided by total volume that moved, over the trades in the window.

The denominator is total volume, the numerator is total notional (price times volume). Both are sums over the window, and both must stay correct as trades enter the front and leave the back.

The window in the literal prompt is a count window: the last N trades. A common follow-up asks the same question over the last K seconds instead, which is a time window. We treat the count window as the core, derive its structure fully, then show how the time window changes only the eviction policy. Holding those two apart is the single most useful distinction in the interview.

A brokerage shows a customer a single price for an instrument they watch. VWAP is the price the market actually paid, weighted by how much volume changed hands at each print. A big trade at a slightly higher price matters more than a tiny trade at a much higher price, because more money moved there. Traders and risk systems watch VWAP over a recent window so the number reflects current conditions, not the whole session.

Why the naive rescanning solution fails

The first instinct is to store the last N trades in a list and, whenever VWAP is asked for, sum price times volume and sum volume over the whole list. That is correct and trivial to write. Its cost is what kills it.

Per query cost of the rescan approach, linear in the window size N.

Every query walks the full window. If the app shows VWAP on every new trade and the window holds ten thousand prints, every trade costs ten thousand multiplications. At a thousand trades per second that is ten million multiplications per second for one symbol, and the work grows with N. The structure is also wasteful on writes, because appending is cheap but the list grows without bound unless you also trim it, and trimming the front of an array list is itself a linear copy in most languages.

The deeper failure is that the rescanning design throws away information it already had. When a new trade arrives and an old trade leaves, almost all the trades in the window are unchanged. Recomputing their contribution is pure waste. The intuition for the optimal design is exactly this: keep the running sums, and adjust them by the one trade that entered and the one trade that left.

The failure compounds when you consider high-frequency streams. A window of ten thousand trades at one thousand trades per second means nine thousand rescan elements survive from the previous query, yet the naive approach sums all ten thousand from scratch. The inefficiency is proportional to the window size, which is exactly the dimension the prompt says to optimize.

The running sums insight

The aha reframe is to stop thinking of VWAP as the average of a list and start thinking of it as two running numbers divided on demand. The numerator and the denominator are each a running sum. When a new trade arrives, you add its notional to the numerator and its volume to the denominator. When an old trade leaves, you subtract its contribution from both. The query is one division.

Each new trade adjusts the two running sums by what entered and what left the window.

The per-trade cost is now constant amortized work: one add and one subtract for each sum, plus the bookkeeping to know which trade left. The query is one division. Memory is still proportional to N, because you must remember the trades currently in the window in order to evict them, but the constant factor is small and the bound is tight.

The optimal sliding window: constant amortized work per trade and constant query, bounded linear memory.

The subtlety is knowing, on every insert, which trade to remove. That is what the data structure must answer in constant time, and it is where the count window and the time window diverge.

Count windows with a ring buffer

In a count window the eviction rule is simple and fixed: when the window holds N trades and a new one arrives, the trade to remove is the oldest one in the window, the one that arrived N inserts ago. Because the index of the evicted trade is fully determined by how many inserts have happened, you do not need to search for it. A ring buffer of size N captures this perfectly: writes go to the next slot, the slot that gets overwritten is exactly the oldest, and the running sums subtract that trade’s contribution just before it is overwritten.

The ring buffer is the right structure for a count window because the eviction site is a pure function of the insert count. Two flat double arrays keep memory predictable: exactly capacity times two doubles plus a few counters, no per-trade object allocation, and the write location is always cache-hot. This is the design you would actually ship in a market-data service.

The amortized constant guarantee deserves one careful word. Each add is genuinely constant work, not just amortized, because there is no resize and no scan. The amortized framing matters when you compare with designs that occasionally compact, which a ring buffer never does.

Time windows with an evicting deque

The follow-up question moves the goalpost. Now the window is the last K seconds, not the last N trades. The eviction rule is no longer a fixed count. It is a timestamp predicate: every trade whose timestamp is older than now minus K must leave. The number of trades in the window varies with arrival rate, so a fixed ring buffer no longer fits.

The structure that fits is a deque of trades ordered by arrival time, plus the same two running sums. On every insert you append the new trade at the tail, then walk the head and pop every trade whose timestamp fell out of the window, subtracting each from the running sums as it leaves. Because timestamps are monotonic in arrival order, every evicted trade is at the head, and once you meet a trade young enough to stay, every trade behind it is younger still, so the eviction loop stops.

The amortized argument for the time window is the standard deque argument. Every trade is added once and removed at most once, so across M inserts the total eviction work is O(M), and each insert is amortized constant.

Each trade is inserted once and evicted at most once, so the per-insert work is amortized constant.

The memory bound is no longer a fixed capacity. It is the number of trades that arrived within the window, which is unbounded if the arrival rate spikes. That is the engineering hazard of the time window, and it is what the next section addresses.

Time windows are unbounded under burst

A count window has a hard memory ceiling because capacity is fixed. A time window does not. A burst of prints within K seconds can fill memory proportional to the burst size. If the prompt allows it, bound the time window with a maximum capacity too, or sample and recompute, and say so out loud.

Concurrency and the shared window

The prompt describes an unbounded stream of trades from a source that is almost certainly multi-threaded. Trades arrive from multiple venues, each on its own thread, each calling add() on the same window. The running sums become contended state, and the same lost-update race that plagues the portfolio-value prompt infects the VWAP window.

Two threads can both read the same numerator, both add their trade’s notional, and both write back, with one write overwriting the other. The same happens for the denominator, and the ring buffer’s head and size fields race independently, corrupting the eviction logic into a torn state where trades overwrite the wrong slot. The bug is intermittent, non-deterministic, and impossible to reproduce on a single thread.

The fix depends on the contention level. For a single-symbol window that many threads update, the simplest correct approach is a single-writer principle: one thread owns the window and all others enqueue their trades into a lock-free MPMC queue from which the owner drains. This serializes access without a lock inside the hot add() path and keeps the ring-buffer operations uncontended.

For higher throughput where the drain-and-return pattern adds latency, a better approach is sharding by symbol so each symbol has its own dedicated window and exactly one thread ever writes it. Trade Republic’s real-time pipelines are a Kafka Streams topology computing per-instrument values, each partition mapping to one processing thread, which naturally gives each window single-writer semantics.

Floating point precision and stability

The running-sums trick has a hidden cost the interviewer may probe. You are summing notional values, each a price times a volume, over thousands or millions of trades. Floating point addition is not associative: the order in which you add matters, and repeatedly adding and subtracting large and small values accumulates rounding error. Over a long session the numerator can drift far enough that the VWAP is visibly off, and the drift is not random, it is biased by the magnitudes involved.

Two defenses cover the realistic range. The first is compensated summation (Kahan summation), which tracks a running compensation for the rounding error lost in each addition and adds it back on the next operation. It costs a few extra operations per add and removes most of the drift. The second is fixed-point arithmetic: represent price and volume as integers scaled to a known precision (cents for price, smallest unit for volume), do all summation in 64-bit or 128-bit integers, and convert to a decimal for display only. Integer addition is exact, so there is no drift at all, at the cost of choosing a scale factor up front and avoiding overflow.

Each floating point addition introduces a relative error bounded by half a machine epsilon, and the errors accumulate across the window.

The overflow hazard is real in fixed-point too. A 64-bit integer holding total notional in micro-cents overflows after roughly ten to the thirteen dollars of cumulative flow, which a high-volume symbol can approach in a long session. The defense is periodic rebasing (subtract a known constant from all values and track the offset), or 128-bit integers, or recomputing the sums from scratch on a schedule to reset drift and overflow risk together.

Fixed point for money, float for analytics

When the number feeds a displayed price or a money calculation, use fixed-point integers and sum exactly. When it feeds an analytics or risk view where a small relative error is acceptable, double-precision floats with Kahan summation are usually enough. The choice is part of the answer.

What changes at millions of trades per second

The data structure is now correct and constant amortized, but the prompt explicitly names high throughput. At a million trades per second the bottleneck is no longer the algorithm, it is everything around it: allocation pressure, garbage collection, cache behavior, and contention across threads.

The ring-buffer design already removes per-trade allocation by reusing flat arrays. The next step is to remove the rest of the allocation: trade objects, boxed primitives, temporary sums. In the hot path every value is a primitive held in preallocated arrays, and the running sums are primitive fields on the window object. A language with a managed runtime benefits further from off-heap storage, where the window lives outside the garbage collector’s reach and is never moved or scanned.

When many threads publish trades into one symbol’s window, the running sums become contended state. A lock around every add serializes all updates to that symbol and caps throughput at the lock’s hold time. The alternatives are sharding by symbol so each symbol has its own single-writer window (no contention because only one thread ever writes a given symbol), lock-free compare-and-swap on the running sums (works when the update fits one atomic, harder when it spans two sums), or batching: accumulate trades per thread in a thread-local buffer and fold them into the shared window in batches, trading a little latency for much higher throughput. Trade Republic’s real-time pipelines are exactly this shape, a Kafka Streams topology computing per-instrument values continuously, fanned out to clients.

The memory bound at this scale is the dominant operational concern. A time window that held every print for an hour at a million per second would hold roughly three and a half billion trades, far beyond any reasonable heap. The defenses are the ones a senior candidate names: bound the window with a maximum capacity, downsample by keeping every Nth trade or aggregating into buckets, or move from exact VWAP to an approximate sketch that uses sublinear memory. The honest answer is that exact VWAP over an unbounded time window at unbounded rate is not feasible, and the design must pick a bound and defend it.

Memory of an exact time window grows with the product of arrival rate and window duration, which is the core scaling hazard.

Beyond memory, the single-window single-CPU model itself breaks at extreme scale. If one symbol receives ten million trades per second, even a flat ring-buffer add with one division requires tens of nanoseconds, and ten million operations still saturate a core. The design must partition: shard by symbol and also across CPU cores per symbol, using batching and micro-batching to amortize the per-trade overhead. The interviewer asking about millions per second is probing whether the candidate knows that the algorithm is only one component of a system, and that allocation, contention, and memory dominate at scale.

Common mistakes candidates make

The first mistake is presenting the rescanning solution as the answer. It is correct but it ignores the efficiency the prompt asks for, and it signals that the candidate has not read the whole requirement. The running sums trick is the minimum viable answer.

The second mistake is confusing a count window with a time window. A ring buffer solves the count window because eviction is by index. It does not solve the time window, because eviction is by timestamp and the live set size varies. Using the wrong structure for the window type is a clear miss.

The third mistake is letting the running sums drift without acknowledging floating point error. Summing millions of large notionals in double precision and treating the result as exact is wrong for a money-facing number. The senior answer names the drift and picks fixed-point or Kahan.

The fourth mistake is ignoring the memory bound on a time window. Storing every trade in an unbounded deque under a burst exhausts memory. The defense is a maximum capacity or a downsampling policy, named before the interviewer has to ask.

The fifth mistake is treating throughput as a solved problem once the algorithm is constant time. At millions of trades per second the algorithm is a small fraction of the work; allocation, garbage collection, and contention dominate. A senior answer talks about flat arrays, sharding by symbol, batching, and off-heap storage.

The sixth mistake is ignoring concurrency entirely. The prompt describes a stream, which in practice means multiple threads. A candidate who presents a single-threaded VWAP window without discussing how it behaves under concurrent access has left an implicit assumption unstated, and the interviewer will probe it.

What the interviewer asks next

The first follow-up is almost always the time-window variant. If you solved the count window, expect to redo it for the last K seconds. The expected answer is the deque with head eviction by cutoff timestamp, plus the amortized argument.

The second follow-up probes precision. The interviewer asks what happens to the sums after running for a day. The expected answer is floating point drift, its bias, and the fixed-point or Kahan fix.

The third follow-up probes scale. The interviewer raises the arrival rate to millions per second and asks where the design breaks. The expected answer is that the algorithm holds but memory on a time window does not, so the design must bound the window, shard by symbol, batch updates, and consider approximate sketches.

The fourth follow-up probes concurrency. The interviewer asks how the window behaves when many threads publish. The expected answer names the contention on the running sums and picks the single-writer principle, sharding, lock-free atomics, or batching, and explains the tradeoff each implies.

The final probe is about correctness under disorder. The interviewer asks what happens if trades arrive out of timestamp order, which is realistic from multiple venues. The expected answer is that the head-eviction loop assumes monotonic timestamps and breaks under reordering, so the design either buffers and sorts by timestamp before insertion, or accepts approximate windows with a watermark.

Mastery Questions

Question

Why does the naive rescanning VWAP fail the prompt, and what is the per-query cost?

Question

Why is a ring buffer the right structure for a count window but wrong for a time window?

Question

Walk through the running-sums update for a count window on a full ring buffer.

Question

Why does the time window give amortized constant work per insert, and what is the memory hazard?

Question

What floating point problem arises from maintaining running sums of notional, and how do you fix it?

Question

At millions of trades per second, what dominates cost and how do you keep throughput up?

Question

How do you handle out-of-order or late trades in a time window, and why does the basic deque break?

Answer

It recomputes both sums over the whole window on every query, throwing away the fact that only one trade entered and one left. The per-query cost is $O(N)$ in the window size, so at high arrival rate the multiplication count scales with $N$ times the arrival rate. The fix is to keep running sums and adjust them by what entered and left, dropping query to $O(1)$.

Answer

In a count window the evicted trade is the one inserted N inserts ago, so its slot is a pure function of the insert count and a fixed-size ring buffer overwrites exactly it. In a time window the evicted set is every trade older than now minus K, whose count varies with arrival rate, so a fixed ring buffer cannot hold the right set. A time window needs an arrival-ordered deque with head eviction by cutoff timestamp.

Answer

When the buffer is full, the slot at head holds the oldest trade. Subtract its price times volume from the numerator and its volume from the denominator, write the new trade into that slot (or the next free slot), add the new trade's notional and volume to the sums, advance head modulo capacity, and return the numerator divided by the denominator. Each step is constant work.

Answer

Each trade is appended once and evicted at most once, so across M inserts the total eviction work is $O(M)$, making per-insert work amortized constant. The hazard is that the live set size equals the number of trades that arrived within the window, which is unbounded under a burst, so memory can spike far above any fixed capacity unless a maximum or a downsampling policy bounds it.

Answer

Repeated floating point addition is not associative and accumulates rounding error, which is biased by magnitude, so after a long session the numerator drifts and VWAP is visibly off. The error per add is bounded by about half a machine epsilon. Fix it with Kahan compensated summation (tracks the lost error and adds it back), or with fixed-point integer summation (exact, at the cost of choosing a scale factor and guarding 64-bit overflow via rebasing or 128-bit integers).

Answer

The algorithm is constant, so allocation pressure, garbage collection, cache behavior, and cross-thread contention dominate. Keep trades in flat primitive arrays with no per-trade allocation, store the window off-heap if the runtime is managed, shard by symbol so each symbol has a single-writer window with no contention, and batch thread-local updates before folding them into the shared window to trade latency for throughput.

Answer

The deque's eviction loop assumes timestamps are monotonic in arrival order: it pops from the head until it meets a trade young enough to stay, then stops. A late trade with an old timestamp lands at the tail behind younger trades and is never evicted on time, corrupting the sums. Fix it by buffering and sorting by timestamp before insertion, or by accepting approximate windows with a watermark that closes the window once events older than a threshold can no longer arrive.

Question

Why does the naive rescanning VWAP fail the prompt, and what is the per-query cost?

Answer

It recomputes both sums over the whole window on every query, throwing away the fact that only one trade entered and one left. The per-query cost is $O(N)$ in the window size, so at high arrival rate the multiplication count scales with $N$ times the arrival rate. The fix is to keep running sums and adjust them by what entered and left, dropping query to $O(1)$.

Prev1 / 7Next