An exact k-sample rolling mean needs O(k) storage — when do you accept a constant-memory approximation instead?

## Where the memory actually goes A fixed-window rolling mean is often described as constant space, and for the *aggregate* that is true: the running sum is a single number. The space cost lives elsewhere. To slide, you must subtract the value that just left the window, and to subtract it you must be able to name it. On a stream with no random access, that means retaining the last k readings in a circular buffer — O(k) storage, independent of stream length but linear in the window. That is the whole tension. Fixed windows are the pattern that makes unbounded streams tractable, because memory is set by k rather than by n. But k is a knob, and on constrained hardware someone else is turning it. ## The constraint that makes this a judgment call Put concrete numbers on it, because the decision is entirely about the numbers. A vibration monitor on a deployed fleet has a few hundred bytes of spare working memory. The window length is a customer-facing setting: 60 samples for a fast alarm, and one customer wants an hour of samples for a slow trend. At four bytes per reading, 60 samples is trivial and 3600 samples is roughly 14 kB per channel — over the ceiling by an order of magnitude, on devices already in the field that can only be changed by a firmware campaign. No algorithmic cleverness makes an exact 3600-sample window fit in a few hundred bytes: you cannot evict a value you did not keep. So the decision is about which guarantee to relax. ## The three defensible positions **Cap k and keep exactness.** Publish a maximum window and refuse configurations above it. Cheap, honest, and immediately unpopular with the customer who wanted the hour-long trend. Its virtue is that everything downstream — thresholds, dashboards, incident review — keeps working unchanged. **Pre-aggregate into buckets.** Accumulate readings into fixed time buckets and slide a window over bucket sums instead of over raw samples. Memory becomes O(b) for b buckets, so an hour split into 60 one-minute buckets costs the same as the original 60-sample window. What you give up is edge granularity: the window boundary now moves in bucket-sized jumps, so the reported mean covers somewhere between 59 and 60 minutes of data rather than exactly 60. For a slow trend that is invisible; for a fast alarm it would be unacceptable. This middle option is the one candidates most often fail to reach, and it is usually the right answer when the two extremes are both bad. **Switch to a decaying average.** Update the estimate toward each new reading by a fixed fraction and keep nothing else: O(1) memory, O(1) per update, no eviction and therefore no buffer at all. The cost is conceptual rather than numerical, and it is large. There is no set of samples the value is a mean *of*: the influence of every reading ever seen decays but never reaches zero, so a single spike keeps nudging the output for a long time. Thresholds calibrated against a true k-sample mean do not transfer, because the two statistics respond to the same input with different amplitude and lag. And during an incident review nobody can answer "which readings caused this alarm", because the answer is "all of them, weighted". | Option | Memory | Window edge | Alarm semantics preserved | Forensics | |---|---|---|---|---| | Exact k-sample window | O(k) samples | Exact | Yes | The k samples are on hand | | Bucketed window | O(b) buckets | Blurred by one bucket | Approximately, if b is adequate | Bucket sums only | | Decaying average | O(1) | None — unbounded tail | No, requires recalibration | None | ## What actually decides it Asymptotics do not decide this; three organisational facts do. **What the threshold means.** If the alarm level appears in a contract, a certification document or a customer runbook as "the mean of the last hour", changing the statistic changes what you have promised, and the recalibration is not a code change — it is a re-tuning exercise across every deployed configuration, with a period during which alarms are wrong in both directions. **What incident review needs.** Field teams argue about alarms. An exact window can produce the offending samples; a decaying average cannot. If disputed alarms are common, that forensic property may be worth more than the memory. **What the team can maintain.** The bucketed scheme has real edge cases — partial buckets at start-up, reconfiguration mid-bucket, clock adjustments — and it will be maintained by whoever is on call in two years. A cleverer structure that only its author understands is a liability that does not show up in any complexity bound. ## How to present it The answer an interviewer wants is not a choice, it is a decision procedure: name the ceiling, name the guarantee each option relaxes, propose the bucketed middle ground as the default, and state the condition under which you would move to either extreme — cap k when exactness is contractual, go decaying when the value is a smoothed indicator nobody adjudicates. Then say how you would validate the migration: run the new estimator alongside the exact one where memory permits, and compare alarm decisions on recorded data before changing anything in the field.