Mean, square, efficiency

Implementing online mean and variance with constant memory

This is a medium-difficulty Python coding problem that tests whether you can implement online statistics — computing running mean and sample variance from a stream without storing all historical data. It's the kind of problem quant firms pose when they care about both algorithmic thinking and practical efficiency in real-time systems.

The key insight is that you do not need to keep every data point in memory. Instead, you maintain a small set of accumulators (typically the count, sum, and sum of squares) and update them incrementally as each new sample arrives. The challenge is deriving the recurrence relations that allow you to compute the sample variance correctly while updating only constant-sized state. You must also be careful about numerical stability and the difference between population and sample variance — the denominator matters.

• Welford's online algorithm and its variants
• Bessel's correction and the denominator in sample variance
• Numerically stable accumulation for floating-point data
• O(1) time per update and O(1) space constraint