Running mean and variance from a stream
Prices stream in one at a time. After each tick, report the mean and the (population) variance of all ticks seen so far, using constant memory. The obvious approach, keeping sum and sum of squares and computing mean = sum/n, var = sumsq/n - mean^2, can lose precision badly when prices are large and clustered. Do it stably.
w = RunningStats()
w.update(100) -> mean 100.0, var 0.0
w.update(102) -> mean 101.0, var 1.0
w.update(104) -> mean 102.0, var 2.667 (approx)
Each update must run in time and memory, and stay numerically stable.
Your answer
This one is open-ended. Work it through, then check your reasoning against the full solution.