How do you run a sweep-line peak-concurrency job over a billion events under a memory ceiling?

## Two representations of the same idea Peak concurrency is the maximum of a step function built from `+w`/`-w` deltas. Nothing forces you to compute that maximum by sorting events; sorting is one representation, and at a billion events it stops being the obvious one. **Representation A — sorted event stream.** Materialise `2n` `(coordinate, delta)` records, order them, scan once with a running sum. Time `O(n log n)`, working memory `O(n)`. **Representation B — dense coordinate domain.** If coordinates live in a bounded integer universe of size `U`, allocate a counter per coordinate, add each delta into its bucket in one streaming pass over the raw events, then walk the buckets accumulating a running sum. Time `O(n + U)`, memory `O(U)`, and **no sort at all**. This is the difference-array representation of the same step function; the mechanism belongs to that pattern, but the *choice* between the two is the decision here. ## The decision variables 1. **`U` versus `n log n`.** Per-second buckets over a day are 86,400 counters; over a year, about 31.5 million. Both are small next to a billion events. Nanosecond timestamps, or floating-point coordinates, give an effectively unbounded `U` and rule B out unless you quantise — and quantising is a product decision about the resolution the metric is reported at, not a free optimisation. 2. **Does `U` fit the ceiling?** `O(U)` memory is a hard, predictable number you can compute in advance and put in a capacity plan. `O(n)` is not: it grows with traffic, which is exactly the direction that hurts. 3. **Streaming or batch?** B reads each raw event once and never revisits it, so it works on a live stream and on data too large to store. A must see all events before the scan can begin, so it is inherently batch. 4. **Do you already own the sort?** If a pipeline already delivers events ordered by coordinate — many log pipelines do, or nearly do — representation A costs one linear pass and the whole argument evaporates. Free ordering is the strongest argument for A there is. ## When you are stuck with A and it does not fit Out-of-core, the sweep decomposes cleanly: sort the event file with an external sort, then make one sequential streaming pass with the running sum. The scan needs `O(1)` memory, so *the sort is the entire memory and I/O problem*. The relevant cost lens shifts from comparison counts to passes over storage, and the honest interview answer is that at this size you are budgeting I/O, not CPU. Sharding by coordinate range works and is the usual production shape, with one subtlety that is the actual interview point: **a shard's local running sum starts at zero, but the true count entering that range is whatever was open at its left boundary.** Each shard must be seeded with the carried-in count — the sum of all deltas in every earlier range — before its local maximum means anything. Since the sum of deltas per shard is a single number, one cheap pass over shard-level totals produces every seed, and only then may you combine the shard maxima. Taking the largest of unseeded shard maxima is the classic wrong answer, and it under-reports in exactly the busiest ranges. ## The organisational half of the decision Asymptotics rarely decide this alone. A sharded external sort with carried-in seeding is several moving parts, each with a failure mode, and someone is on call for it at 3 a.m. A bucket-counting job over a fixed 86,400-slot domain is one loop that a new engineer reads correctly on the first try, has memory usage that does not change when traffic doubles, and degrades in an obvious way if the coordinate range assumption breaks. If both meet the batch window, the maintainable one wins, and being able to say *why* — operability and predictable memory beat a better constant factor — is the principal-level part of this answer. The reverse case is real too: if the metric must be reported at full timestamp resolution, or the coordinate domain is unbounded because coordinates are opaque identifiers rather than clock ticks, then B is not available at any price and you build the sorted pipeline properly, including the seeding. ## What to state explicitly before choosing Say out loud which numbers you would go and measure: `n`, the coordinate domain size and its resolution, the memory ceiling per worker, the batch window, and whether ordering already exists upstream. A choice defended by those five is a decision; a choice defended by "`O(n + U)` beats `O(n log n)`" is a guess that happens to have notation attached.