Moving average from a stream

Question

Ticks arrive one at a time from a market-data feed. Design a class that, after each new tick, returns the average of the last k prices seen (or of all prices, if fewer than k have arrived).

m = MovingAverage(k=3)
m.update(10)  -> 10.0
m.update(20)  -> 15.0
m.update(30)  -> 20.0
m.update(40)  -> 30.0      # window is now [20, 30, 40]

Each update must run in $O(1)$ time and the class must use $O(k)$ memory.

Accepted Answer

Keep the current window in a deque and maintain its running sum. On each update, append the new price, add it to the sum, and if the window has grown past k, pop the oldest price from the left and subtract it. Both deque operations are O(1). Tracing k = 3: after 10, 20, 30 the window holds all three and the mean is 20.0; on 40 the 10 is evicted, leaving [20, 30, 40] with mean 30.0. O(1) per update, O(k) space. Two follow-ups interviewers like: (1) floating-point drift, after millions of add/subtract updates total slowly diverges from the true window sum, so recompute it every N updates or use…

Moving average from a stream

Your answer

More Coding questions