Time-Series Event Aggregation And Rolling Windows

What's being tested

This topic tests whether you can turn a stream of timestamped events into efficient time-windowed aggregates without rescanning historical data for every query. The interviewer is probing your command of sliding windows, timestamp ordering, expiration policies, data structures, and complexity under high event rates. At Hudson River Trading, the same reasoning supports low-latency monitoring, rolling risk or volume calculations, and real-time decision systems where predictable p99 latency matters.

Core knowledge

A tumbling window partitions time into fixed, non-overlapping intervals, while a sliding window covers the continuously preceding interval $[t-W,t]$ . Tumbling windows are simpler; sliding windows provide fresher results but require explicit expiration.
For monotonically processed timestamps, maintain a deque of events ordered by time and a running aggregate. On each event at time $t$ , append it, evict entries with timestamp < t-W, and update the aggregate in O(1) amortized time.
The standard sliding-window invariant is: every stored event satisfies timestamp >= current_time - window_size. State the boundary convention explicitly—closed windows use <=, while half-open windows commonly use $[t-W,t)$ —because off-by-one errors change counts.
For sums and counts, maintain running_sum and len(deque). For averages, use running_sum / count; define behavior for an empty window instead of returning an accidental divide-by-zero or stale value.
Monotonic queues compute rolling minimum or maximum in O(n) total time: remove dominated values from the back, append the new value, and remove expired indices from the front. Store (timestamp, value) or (index, value) so expiration is precise.
If events arrive already sorted by timestamp, each item is inserted and removed once, yielding O(n) time and O(k) space for at most k events in a window. A naïve query that scans the window costs O(nk) over n events.
For arbitrary historical queries, use prefix sums or an indexed structure. With sorted arrays, binary search finds window boundaries in O(log n) and prefix differences answer sums in O(1); updates require a Fenwick tree or segment tree.
A ring buffer is effective when timestamps are quantized into fixed buckets and the maximum window is bounded. It provides predictable memory and constant-time bucket rotation, but loses event-level precision unless each bucket stores sufficient detail.
For multiple keys, such as instrument or account, maintain independent per-key state: Map<Key, WindowState>. Bound memory with inactivity eviction, maximum cardinality, or a clearly stated assumption about the active-key set.
Different aggregates have different data-structure requirements. Sum, count, and bitwise operations support easy insertion and deletion; median or percentile needs two heaps, an order-statistics tree, or an approximate sketch such as t-digest, because arbitrary deletion is harder.
Distinguish processing time from event time. If the algorithm must answer “what was true at timestamp t?” then the design needs ordered insertion, buffering, or a bounded-lateness policy; otherwise, state that input timestamps are nondecreasing and reject or separately handle older events.
Test boundaries and operational behavior: empty input, one event, equal timestamps, events exactly at the cutoff, a window larger than all history, negative values, duplicate events, timestamp overflow, idle periods, and memory growth from many active keys.

Worked example

No specific interview-question title was supplied, so use this representative prompt: “Maintain the number of events seen for each key during the last five minutes.” In the first 30 seconds, clarify whether timestamps are nondecreasing, whether the interval is inclusive, whether queries are per key or global, and what to do with unknown or late timestamps. I would state the invariant that each key stores only events in [now - 5 minutes, now], then organize the answer around data representation, insertion and expiration, complexity, and correctness tests. The baseline implementation is a per-key deque plus count, evicting expired entries whenever a new event or query advances that key’s current time. The main tradeoff is between exact event-level storage and bucketed storage: deques preserve precision, while buckets reduce memory and improve cache behavior at the cost of boundary accuracy. I would call out that lazy expiration means an idle key can retain stale entries, so queries must expire state before returning and inactive keys may need cleanup. I would close by saying that, with more time, I would specify behavior for out-of-order events and add benchmarks for active-key cardinality, event rate, and p99 query latency.

A second angle

A rolling maximum over the last W samples uses the same expiration invariant but cannot use a simple running sum. A monotonic deque removes smaller values from the back because they can never become the maximum while the larger value remains active, and removes expired timestamps from the front. The result is O(n) total time and O(W) space, unlike repeatedly scanning each window in O(nW). If arbitrary inserts and deletions are required, the monotonic-queue assumption breaks and an order-statistics structure may be preferable.

Common pitfalls

Pitfall: Treating a rolling window as “the last N events” when the requirement is “the last W seconds.” Event density can vary, so count-based eviction produces incorrect results unless the specification explicitly defines a sample window.

A tempting answer is to store every event and scan the deque on every query. That is functionally correct but often misses the point: maintain incremental state and prove amortized complexity, while acknowledging the memory cost of retaining events until expiration.

Pitfall: Saying “late events are impossible” without stating it as an assumption.

A strong response either declares monotonically ordered input or explains a bounded-lateness policy, such as buffering, rejecting events older than the retained horizon, or rebuilding affected state. Do not casually promise exact results for arbitrary out-of-order updates with a data structure designed only for append-at-the-tail processing.

Connections

An interviewer may pivot to monotonic queues, Fenwick trees, segment trees, approximate quantiles, or event-time versus processing-time semantics. They may also ask how to shard per-key state, preserve ordering, or expose consistent snapshots without turning the answer into an unbounded global lock.