Streaming and online algorithms

intermediateCommon atAnthropicGoogleMetaStripeRead firstHeapsHash mapsSliding windowPractise in the Sandbox →

A streaming (or online) algorithm reads each item once, in arrival order, and keeps a small summary instead of the data. The invariant: after every item, the summary answers the question for everything seen so far. Exact answers like mean and variance fit in O(1) memory; others (median, distinct count, frequencies) need O(n) to be exact, so at scale you trade a little accuracy for fixed memory.

The idea in plain words

Think of a turnstile clicker at a stadium gate. It doesn’t remember faces. It keeps one number, and that number is always the right answer to “how many people came in?”.

A streaming algorithm is a smarter clicker. You decide what question you need answered, then ask: what is the least I must remember so I can update the answer when one more item arrives?

• Count, sum, min, max: one number each. Trivial.
• Mean and variance: three numbers (count, mean, a running “spread” total). This is Welford’s method.
• Median: no small summary exists. You must keep the values, but you can keep them organised so each update is O(log n).
• “How often did X appear?” / “How many distinct?” over billions of items: exact needs memory per distinct item. Sketches (count-min, HyperLogLog) answer approximately in a few kilobytes.

Two words you will hear. Online means you must answer after each item without seeing the future (like a live dashboard). One pass means you may only read the input once, perhaps because it is a 2 TB log file or a network socket.

See it

Type a stream, then step through. The left panel shows Welford’s three numbers: they never grow. The right panel keeps the exact median with two halves (a max-heap of the smaller half and a min-heap of the larger half). Watch the halves stay within one element of each other, and notice that they hold every value.

One pass: running mean, variance and median

step through

stream (≤ 18 values)

·

·

·

·

·

·

·

·

·

·

dimmed = already consumed; dashed = not arrived yet

Welford: O(1) memory

n0

mean0

M20

variance0

stddev0

Two halves: median = –

lower half · max-heap, biggest on top

(empty)

upper half · min-heap, smallest on top

(empty)

arriving nowheap topjust changed

Values arrive one at a time and are never revisited. Welford keeps 3 numbers; the median keeps two halves.

↺◀▶ Play▶1 / 16

When exact is too expensive, you sketch. A count-min sketch keeps a small grid of counters. Each item bumps one counter in every row (picked by a different hash per row). Collisions only ever add, so each counter is an over-estimate, and the smallest of an item’s counters is the best guess.

Count-min sketch: approximate counts in a fixed grid

sandbox

stream of words

+12 other wordsclear

width w (columns) = 8depth d (rows) = 3

0

7

0

0

0

1

0

0

0

1

1

4

0

0

0

2

0

4

0

3

1

0

0

0

Each word bumps one counter per row. Highlighted: the 3 counters for cat; green is the minimum, the estimate.

word	true count	estimate	over by
cat	4	4	0
dog	2	2	0
bird	1	1	0
fish	1	1	0

items8

distinct4

counters24

total over-count0

Click a row to see its counters. Shrink the width or add other words: collisions push estimates up, never down. Add rows and the minimum filters most collisions out.

the word's counter in a rowsmallest one = estimate

A HyperLogLog estimates how many distinct items it saw. Drag n from 10 to 200,000: the memory stays at m registers, while the error stays near ±1.04/√m.

HyperLogLog: count distinct items with a few hundred bytes

drag the sliders

distinct items n = 1,000

registers m1664256new hash seed

true n1,000

estimate1,125

error+12.5%

typical error±13.0%

memory64 × 6 bits = 48 B

exact set would need~32,000 B

Flip a fair coin until heads: a run of k tails before the first head turns up about once in 2^k tries. So the longest run you have seen (11 zeros, amber) hints that you saw about 2¹¹ things. One register is noisy; HyperLogLog splits items over m registers and takes a harmonic mean, so the error shrinks like 1.04/√m.

When to reach for it

The problem says…	Why streaming fits
“the input does not fit in memory” / “a 500 GB log file”	One pass with a summary is the only way to avoid loading it.
“after each event, report…” / “live dashboard”	An online algorithm updates the answer per item instead of recomputing.
“running average / standard deviation”	Welford: O(1) memory, numerically stable.
“median so far” with frequent queries	Two heaps: O(log n) per insert, O(1) per query.
“approximately how many distinct users / how often” over huge volume	Sketches give bounded error in fixed memory.
“pick k random lines from a file of unknown length”	Reservoir sampling, one pass, O(k) memory.

How it works

Running mean and variance (Welford)

The textbook variance formula, mean of squares minus square of mean, is one pass but numerically unstable: with values near 10⁹, both terms are about 10¹⁸ and their difference (the variance you want) disappears in floating-point rounding. Welford updates the mean and a running sum of squared deviations directly.

1. Count the new value: n += 1.
2. Measure how far it is from the old mean: delta = x - mean.
3. Move the mean a fraction of the way: mean += delta / n.
4. Grow the spread by old distance times new distance: M2 += delta * (x - mean). Variance is M2 / (n - 1) (sample) or M2 / n (population).

Python

RunningStats.py

import math


class RunningStats:
    """Mean and variance of a stream in one pass and O(1) memory (Welford, 1962)."""

    def __init__(self) -> None:
        self.n = 0
        self.mean = 0.0
        self.m2 = 0.0  # sum of squared distances from the current mean

    def push(self, x: float) -> None:
        self.n += 1                      # 1. count the new value
        delta = x - self.mean            # 2. distance from the OLD mean
        self.mean += delta / self.n      # 3. nudge the mean toward x
        self.m2 += delta * (x - self.mean)  # 4. old distance x new distance: no big sums to cancel

    def variance(self) -> float:
        """Sample variance (divide by n - 1). Needs at least two values."""
        return self.m2 / (self.n - 1) if self.n > 1 else 0.0

    def stddev(self) -> float:
        return math.sqrt(self.variance())


if __name__ == "__main__":
    s = RunningStats()
    for x in [2, 4, 4, 4, 5, 5, 7, 9]:
        s.push(x)
    assert s.n == 8 and s.mean == 5.0
    assert abs(s.variance() - 32 / 7) < 1e-12  # population var is 4, sample var 32/7
    # Large offset: the naive sum(x^2)/n - mean^2 formula loses every digit here.
    big = RunningStats()
    for x in [1e9 + 4, 1e9 + 7, 1e9 + 13, 1e9 + 16]:
        big.push(x)
    assert abs(big.variance() - 30.0) < 1e-6
    print("ok")

TypeScript

RunningStats.ts

import assert from "node:assert/strict";

/** Mean and variance of a stream in one pass and O(1) memory (Welford, 1962). */
export class RunningStats {
  n = 0;
  mean = 0;
  m2 = 0; // sum of squared distances from the current mean

  push(x: number): void {
    this.n += 1; // 1. count the new value
    const delta = x - this.mean; // 2. distance from the OLD mean
    this.mean += delta / this.n; // 3. nudge the mean toward x
    this.m2 += delta * (x - this.mean); // 4. old distance x new distance: no big sums to cancel
  }

  /** Sample variance (divide by n - 1). Needs at least two values. */
  variance(): number {
    return this.n > 1 ? this.m2 / (this.n - 1) : 0;
  }

  stddev(): number {
    return Math.sqrt(this.variance());
  }
}

const s = new RunningStats();
for (const x of [2, 4, 4, 4, 5, 5, 7, 9]) s.push(x);
assert.equal(s.n, 8);
assert.equal(s.mean, 5);
assert.ok(Math.abs(s.variance() - 32 / 7) < 1e-12); // population var is 4, sample var 32/7
// Large offset: the naive sum(x^2)/n - mean^2 formula loses every digit here.
const big = new RunningStats();
for (const x of [1e9 + 4, 1e9 + 7, 1e9 + 13, 1e9 + 16]) big.push(x);
assert.ok(Math.abs(big.variance() - 30) < 1e-6);
console.log("ok");

C#

RunningStats.cs

var s = new RunningStats();
foreach (var x in new double[] { 2, 4, 4, 4, 5, 5, 7, 9 }) s.Push(x);
if (s.N != 8 || s.Mean != 5.0) throw new Exception("expected n=8, mean=5");
if (Math.Abs(s.Variance() - 32.0 / 7) > 1e-12) throw new Exception("expected 32/7"); // population var is 4
// Large offset: the naive sum(x^2)/n - mean^2 formula loses every digit here.
var big = new RunningStats();
foreach (var x in new[] { 1e9 + 4, 1e9 + 7, 1e9 + 13, 1e9 + 16 }) big.Push(x);
if (Math.Abs(big.Variance() - 30.0) > 1e-6) throw new Exception("expected 30");
Console.WriteLine("ok");

/// Mean and variance of a stream in one pass and O(1) memory (Welford, 1962).
sealed class RunningStats
{
    public long N { get; private set; }
    public double Mean { get; private set; }
    double _m2; // sum of squared distances from the current mean

    public void Push(double x)
    {
        N++;                          // 1. count the new value
        double delta = x - Mean;      // 2. distance from the OLD mean
        Mean += delta / N;            // 3. nudge the mean toward x
        _m2 += delta * (x - Mean);    // 4. old distance x new distance: no big sums to cancel
    }

    /// Sample variance (divide by n - 1). Needs at least two values.
    public double Variance() => N > 1 ? _m2 / (N - 1) : 0.0;
    public double StdDev() => Math.Sqrt(Variance());
}

Two summaries can merge

Welford states from two shards combine exactly (Chan et al.): n = na + nb, delta = mean_b - mean_a, mean = mean_a + delta * nb / n, M2 = M2a + M2b + delta² * na * nb / n. “Can my summary merge?” is the question that decides whether a streaming algorithm also works in parallel.

Median: why it cannot be O(1) memory

Any exact one-pass median needs memory proportional to n in the worst case (Munro and Paterson proved this lower bound in 1980): until the stream ends, any value you threw away might turn out to be the middle one. The standard exact structure is the two-heaps idea you stepped through above:

• The lower half lives in a max-heap, so its biggest value is on top.
• The upper half lives in a min-heap, so its smallest value is on top.
• Invariant: every value in the lower half ≤ every value in the upper half, and the sizes differ by at most one. Then the median is one top, or the average of the two tops.

Each new value goes into one heap and may cause one value to move across: O(log n) per item, O(1) to read the median. For bounded memory at scale, systems use approximate quantile sketches instead (Greenwald-Khanna, t-digest, KLL), which answer “the 99th percentile” within a stated rank error.

Stdlib heaps

Python’s heapq is a min-heap only; store negated values for a max-heap. .NET has PriorityQueue<TElement, TPriority> (a min-heap on priority; pass a reversed Comparer for max). TypeScript/JavaScript has no built-in heap, so in an interview you write a small binary heap or say you would. See Heaps.

Count-min sketch

1. Allocate depth rows of width counters, all zero, and pick one hash function per row.
2. To add an item, hash it once per row and increment that row’s counter.
3. To estimate an item, read its counter in every row and return the minimum. Collisions only inflate counters, so the error is one-sided: never too low.

Python

CountMinSketch.py

class CountMinSketch:
    """Approximate counts in fixed memory: depth rows x width counters.
    Never under-counts; over-counts by at most ~ e/width * total with high probability."""

    def __init__(self, width: int, depth: int) -> None:
        self.width, self.depth = width, depth
        self.rows = [[0] * width for _ in range(depth)]

    def _col(self, item: str, row: int) -> int:
        # FNV-1a, with a different starting value per row, so rows collide differently.
        h = (2166136261 ^ (row * 0x9E3779B9)) & 0xFFFFFFFF
        for b in item.encode():
            h = ((h ^ b) * 16777619) & 0xFFFFFFFF
        return h % self.width

    def add(self, item: str, count: int = 1) -> None:
        for r in range(self.depth):          # 1. one counter per row goes up
            self.rows[r][self._col(item, r)] += count

    def estimate(self, item: str) -> int:
        # 2. every row over-counts (collisions only add), so the smallest is the best guess
        return min(self.rows[r][self._col(item, r)] for r in range(self.depth))


if __name__ == "__main__":
    words = "the cat sat on the mat the end the cat".split()
    cms = CountMinSketch(width=16, depth=3)
    for w in words:
        cms.add(w)
    true = {w: words.count(w) for w in words}
    for w, c in true.items():
        assert cms.estimate(w) >= c          # one-sided error: never too low
    assert all(sum(row) == len(words) for row in cms.rows)  # every row saw every item
    assert cms.estimate("the") == 4
    print("ok")

TypeScript

CountMinSketch.ts

import assert from "node:assert/strict";

/** Approximate counts in fixed memory: depth rows x width counters.
 *  Never under-counts; over-counts by at most ~ e/width * total with high probability. */
export class CountMinSketch {
  readonly rows: Uint32Array[];
  private static enc = new TextEncoder();

  constructor(readonly width: number, readonly depth: number) {
    this.rows = Array.from({ length: depth }, () => new Uint32Array(width));
  }

  private col(item: string, row: number): number {
    // FNV-1a, with a different starting value per row, so rows collide differently.
    let h = (2166136261 ^ Math.imul(row, 0x9e3779b9)) >>> 0;
    for (const b of CountMinSketch.enc.encode(item)) h = Math.imul(h ^ b, 16777619) >>> 0;
    return h % this.width;
  }

  add(item: string, count = 1): void {
    for (let r = 0; r < this.depth; r++) this.rows[r][this.col(item, r)] += count; // 1. one counter per row
  }

  estimate(item: string): number {
    // 2. every row over-counts (collisions only add), so the smallest is the best guess
    let best = Infinity;
    for (let r = 0; r < this.depth; r++) best = Math.min(best, this.rows[r][this.col(item, r)]);
    return best;
  }
}

const words = "the cat sat on the mat the end the cat".split(" ");
const cms = new CountMinSketch(16, 3);
for (const w of words) cms.add(w);
for (const w of new Set(words)) {
  assert.ok(cms.estimate(w) >= words.filter((x) => x === w).length); // never too low
}
for (const row of cms.rows) assert.equal(row.reduce((a, b) => a + b, 0), words.length);
assert.equal(cms.estimate("the"), 4);
console.log("ok");

C#

CountMinSketch.cs

using System.Text;

var words = "the cat sat on the mat the end the cat".Split(' ');
var cms = new CountMinSketch(width: 16, depth: 3);
foreach (var w in words) cms.Add(w);
foreach (var w in words.Distinct())
    if (cms.Estimate(w) < words.Count(x => x == w)) throw new Exception($"under-count for {w}"); // never too low
foreach (var row in cms.Rows)
    if (row.Sum() != words.Length) throw new Exception("every row should see every item");
if (cms.Estimate("the") != 4) throw new Exception("expected 4");
Console.WriteLine("ok");

/// Approximate counts in fixed memory: depth rows x width counters.
/// Never under-counts; over-counts by at most ~ e/width * total with high probability.
sealed class CountMinSketch(int width, int depth)
{
    public int[][] Rows { get; } = Enumerable.Range(0, depth).Select(_ => new int[width]).ToArray();

    int Col(string item, int row)
    {
        // FNV-1a, with a different starting value per row, so rows collide differently.
        uint h = 2166136261u ^ unchecked((uint)row * 0x9E3779B9u);
        foreach (byte b in Encoding.UTF8.GetBytes(item)) h = unchecked((h ^ b) * 16777619u);
        return (int)(h % (uint)width);
    }

    public void Add(string item, int count = 1)
    {
        for (int r = 0; r < depth; r++) Rows[r][Col(item, r)] += count; // 1. one counter per row
    }

    // 2. every row over-counts (collisions only add), so the smallest is the best guess
    public int Estimate(string item) => Enumerable.Range(0, depth).Min(r => Rows[r][Col(item, r)]);
}

Sizing comes from Cormode and Muthukrishnan: with width = ⌈e / ε⌉ and depth = ⌈ln(1/δ)⌉, every estimate is at most true + ε·N (N = total count) with probability at least 1 − δ. For ε = 0.1% and δ = 1%, that is 2,719 × 5 counters: about 54 KB of 32-bit counters, whatever the number of distinct items.

HyperLogLog (intuition)

Hash each item to random-looking bits. In random bits, a run of k leading zeros appears about once every 2^k values, so the longest run you have seen estimates log₂ of the distinct count. Duplicates hash identically, so they never change the answer: that is why it counts distinct items. One such estimate is very noisy, so HyperLogLog uses the first few bits to pick one of m registers, keeps the longest run per register, and combines them with a harmonic mean plus a correction factor. Standard error is about 1.04 / √m. Redis uses m = 16,384 registers in 12 KB for 0.81% error. Registers merge by taking the maximum, so sketches from many servers combine exactly.

Reservoir sampling (prose only)

To keep a uniform random sample of k items from a stream of unknown length: keep the first k; for item number i > k, with probability k / i replace a uniformly random slot. Each item ends up in the sample with probability exactly k / n (Vitter’s Algorithm R, from Knuth).

What it costs

Question	Exact, one pass	Memory	Approximate alternative
count, sum, min, max	yes	O(1)
mean, variance (Welford)	yes	O(1)
median / percentile	two heaps, O(log n) per item	O(n)	GK / t-digest / KLL: O(1/ε · polylog)
frequency of an item	hash map of counts	O(distinct)	count-min: O(1/ε · log 1/δ), over-counts only
distinct count	hash set	O(distinct)	HyperLogLog: m registers, ±1.04/√m
top-k heavy hitters	full count map + heap	O(distinct)	Misra-Gries / Space-Saving: O(k)
uniform sample of k	reservoir	O(k)

The pattern: anything you can write as a fold with a small accumulator (state = update(state, x)) streams in O(1). Anything that depends on the rank or identity of many items needs memory for those items, unless you accept a bounded error.

Variations you’ll meet

• Windowed streams. “Over the last 5 minutes” instead of “ever”. Old items must expire: keep a queue of buckets or timestamps and subtract what falls out (see Sliding window and TTL and expiry). Welford can be reversed to remove a value, though removal is less numerically stable than adding.
• Exponentially weighted averages. avg = α·x + (1 − α)·avg forgets old data smoothly in O(1), with no window to store. Common in load balancers and latency trackers.
• Merging sorted streams. k sorted inputs into one sorted output with a heap of k heads: O(log k) per item.
• Out-of-order and late data. Real streams arrive late. Systems keep a “grace period” or watermark and decide what to do with items older than it.
• Heavy hitters. Misra-Gries keeps k − 1 counters and guarantees any item with frequency > n/k survives.

Pitfalls

• Naive variance (E[x²] − E[x]²) on large or similar values returns garbage, even negative numbers. Use Welford.
• Integer division and overflow. A running sum of int32 values overflows quickly in C#; use long. In TypeScript every number is a double, exact only up to 2^53.
• Pretending the median is O(1) memory. It is not. Say so, then offer an approximation if memory is bounded.
• Under-sized sketches. A count-min sketch narrower than the number of heavy items reports large errors. Size it from ε and δ, and remember the error scales with total volume N.
• Weak hash functions correlate rows and break the guarantees. Use independent seeds.
• Reading the whole file anyway. f.readlines(), File.ReadAllLines and JSON.parse on the whole input load everything. Iterate lines instead (see Memory efficiency).

In the interview

• Ask: does it fit in memory? Is it one pass or can I read twice? Do I need exact answers? Is there a time window? Do items arrive in order?
• Name the summary and its invariant out loud: “After each item, mean is the mean of everything so far and M2 is the sum of squared deviations from it.”
• Separate exact from approximate explicitly and quote the bound: “count-min never under-counts; it over-counts by at most ε·N with probability 1 − δ.”
• Expect follow-ups: make it windowed, run it on 100 machines and merge, what if memory is capped at 1 MB, what if data arrives late.

Check yourself

Check yourself

pick one

You compute variance in one pass as sum(x²)/n − mean². The values are all near 1,000,000,000 and differ by a few units. What happens?

AIt is exact, just slower than WelfordBBoth terms are ~10¹⁸ and the tiny difference is lost to rounding; the result can be wildly wrong or negativeCIt overflows to infinity

Check yourself

pick one

A count-min sketch reports 57 for item X. What can you say about X's true count?

AIt is exactly 57BIt is at most 57CIt is at least 57DNothing; the error can go either way

Check yourself

pick one

Why does HyperLogLog count distinct items rather than total items?

AIt stores a hash set internallyBA repeated item hashes to the same bits, so it can never raise a register beyond what its first occurrence didCIt divides the total by the average frequency

Practice on your own

These are classic textbook exercises, not gym questions:

• Merge two Welford summaries computed on different halves of an array; check against a two-pass variance.
• Reservoir-sample k lines from a file of unknown length; test uniformity by sampling a 10-line file 100,000 times.
• Misra-Gries: find every element that appears more than n/3 times in one pass with two counters.
• Exponential moving average of request latency; compare its reaction to a spike against a 10-item simple moving average.
• Estimate distinct words in a large text with a 64-register HyperLogLog; compare to a set.

Go deeper

• Wikipedia: Algorithms for calculating variance, Welford’s update, the parallel merge (Chan et al.) and why the naive formula fails. Also Knuth, TAOCP vol. 2, §4.2.2.
• Cormode and Muthukrishnan, An improved data stream summary: the count-min sketch and its applications (2005).
• Flajolet, Fusy, Gandouet and Meunier, HyperLogLog: the analysis of a near-optimal cardinality estimation algorithm (2007), and Redis HyperLogLog docs for a production setting.
• Vitter, “Random sampling with a reservoir”, ACM TOMS 11(1), 1985.

Related

HeapsThe structure behind the exact running median and k-way merges.

Sliding windowStreams with a time horizon: add on the right, expire on the left.

Memory efficiencyBytes per element, and streaming instead of loading.

Distributed systems reasoningMergeable summaries let shards compute statistics in parallel.