Streaming Algorithms And Online Aggregation

What's being tested

Streaming algorithms and online aggregation test whether you can compute useful answers over unbounded, high-velocity data without storing every event. The interviewer is probing algorithm selection, error guarantees, memory/latency tradeoffs, mergeability across workers, and behavior under duplicates, out-of-order arrivals, and changing time windows. For a Software Engineer at OpenAI, this matters when building low-latency telemetry, usage limits, evaluation dashboards, safety counters, and operational metrics where exact batch recomputation is too slow or expensive.

Core knowledge

Online aggregation processes each item once, maintaining a compact state rather than retaining the full stream. State should support update(event), query(), and ideally merge(other) so independently processed partitions can be combined.
Exact counters and sums require $O(1)$ state per key, but unbounded distinct keys require storage proportional to cardinality. For bounded keyspaces, use sharded maps and atomic increments; for millions of keys, explicitly discuss eviction, quotas, or approximate summaries.
Welford’s algorithm computes a numerically stable mean and variance online. For each value $x_n$ , update $\delta=x_n-\mu_{n-1}$ , $\mu_n=\mu_{n-1}+\delta/n$ , and $M_{2,n}=M_{2,n-1}+\delta(x_n-\mu_n)$ ; variance is $M_2/(n-1)$ .
Count-Min Sketch estimates item frequency using $d$ hash rows and width $w$ . It guarantees, with probability at least $1-\delta$ , overestimation error roughly $\epsilon N$ when $w\approx e/\epsilon$ and $d\approx\ln(1/\delta)$ ; it never underestimates, assuming nonnegative updates.
Heavy hitters can be found with a Count-Min Sketch plus a candidate set, or with Space-Saving. A sketch alone does not identify which keys are frequent; retaining candidates, sampling keys, or maintaining a heap is necessary for top- $K$ queries.
HyperLogLog estimates distinct cardinality using $m$ registers and leading-zero statistics. Its relative standard error is approximately $1.04/\sqrt m$ ; union is mergeable by register-wise maximum, making it useful across workers and shards.
Reservoir sampling maintains a uniform sample of $k$ items from an unknown-length stream using $O(k)$ memory. Keep the first $k$ items; for item $i>k$ , replace a random reservoir element with probability $k/i$ . The result is unbiased only if every item has equal sampling eligibility.
Sliding windows are different from lifetime aggregates. Exact time windows need expiring state, commonly ring buffers of fixed buckets; approximate windows use tumbling or hopping buckets. A five-minute tumbling window can have boundary artifacts, while hopping windows improve smoothness at higher compute cost.
Exponential decay emphasizes recent events without explicit expiration: $A_t=\lambda^{\Delta t}A_{\text{previous}}+x_t$ , where $0<\lambda<1$ . Choose half-life $h$ with $\lambda=e^{-\ln 2/h}$ ; this is efficient but does not represent a strict “last five minutes” count.
Mergeability is a central design criterion. Sums, counts, min/max, HyperLogLog, and compatible sketches merge naturally; medians and exact quantiles do not. For quantiles, use t-digest or KLL sketches, and state their approximation behavior rather than claiming exactness.
Approximate quantiles must distinguish rank error from value error. A rank-error guarantee says the returned value is near position $qN$ in sorted order; this is more meaningful than a fixed numeric error when latency distributions span milliseconds to hours.
Distributed correctness requires deciding how duplicates and retries behave. Use event IDs with deduplication when exact counting matters, or design updates to be idempotent; “at-least-once delivery plus increment” can inflate counters. State whether results are immediately consistent, eventually consistent, or bounded-stale.
Numerical and operational limits matter: use 64-bit counters, guard timestamp overflow, define behavior for negative updates, and monitor sketch saturation. Memory should be estimated explicitly—for example, a sketch with $d=7$ and $w=20{,}000$ needs about 140,000 counters before metadata and sharding overhead.

Worked example

Because no concrete interview prompt was supplied, use this representative prompt: “Design an online aggregation API for request metrics.” In the first 30 seconds, clarify whether the API needs exact counts, distinct users, percentiles, or top endpoints; define acceptable error, freshness, retention window, event volume, and duplicate semantics. I would organize the answer around four pillars: per-key state, time-window representation, horizontal partitioning and mergeability, and query latency plus operational safeguards. For exact request counts over a bounded set of metrics, I would use sharded counters; for distinct users, HyperLogLog; and for latency percentiles, a mergeable KLL or t-digest rather than storing samples indefinitely. I would partition updates by metric key, periodically merge shard summaries, and expose the timestamp or window represented by each result. The key tradeoff is exactness versus memory: exact five-minute per-endpoint percentiles may be too expensive, while an approximate sketch can provide a documented rank-error bound with predictable memory. I would explicitly address retries by requiring event IDs or accepting bounded overcounting if the source is at-least-once. If I had more time, I would specify hot-key mitigation, snapshot and recovery behavior, benchmark update/query p99, and test error against an exact offline computation.

A second angle

A different representative prompt is “Maintain the top 100 most-used tokens from an unbounded stream.” The framing shifts from general metric aggregation to identifying keys, so a simple counter is insufficient: the algorithm needs candidate retention and replacement. A Count-Min Sketch can estimate frequencies compactly, while a min-heap or Space-Saving structure maintains likely heavy hitters. The important constraint is that approximate frequency estimates may reorder near-tied items, so the API should document that the returned boundary is not exact. In a distributed deployment, merge behavior and candidate reconciliation become as important as per-event update cost.

Common pitfalls

Pitfall: Saying “use a hash map” for every stream problem ignores unbounded cardinality and can turn a constant-time update into an eventual out-of-memory failure. State when exact state is bounded, and choose a sketch, sampling method, TTL, or eviction policy when it is not.

Pitfall: Claiming that a Count-Min Sketch gives exact counts, or that HyperLogLog returns exact distinct users, is a serious analytical error. Name the direction of bias, error metric, confidence or relative-error bound, and how you would validate approximation against a smaller exact sample.

Pitfall: Jumping directly to Kafka, databases, and deployment diagrams without first clarifying the aggregate, window, freshness, and duplicate requirements misses the algorithmic decision. Start with the state transition and correctness contract, then map it onto distributed components.

Connections

An interviewer may pivot to consistent hashing, idempotency, checkpointing, and fault recovery, or to rate limiting algorithms such as token bucket and leaky bucket. They may also connect this topic to distributed snapshots, approximate quantiles, and observability systems such as Prometheus, where cardinality control and label design directly affect memory and query cost.

Visa Tools

Visa Sponsors

H-1B Odds Calculator

Visa Bulletin