Moving Average from Data Stream

Moving Average from Data Stream

What is this problem about?

The Moving Average from Data Stream problem asks you to design a class that computes the moving average of the last k elements of a data stream. Each time a new number arrives, add it to the window and remove the oldest if the window exceeds size k. Return the current average. This Moving Average from Data Stream coding problem tests circular buffer or queue design.

Why is this asked in interviews?

Nuro, Tesla, Citadel, Microsoft, Meta, Amazon, LinkedIn, Google, and Bloomberg ask this because moving averages are fundamental to real-time data processing, stock market analytics, and signal smoothing. The data stream, array, design, and queue interview pattern is the core, and the problem tests whether candidates can implement a sliding window cleanly with O(1) per-operation complexity.

Algorithmic pattern used

Circular queue (deque or fixed array). Maintain a queue of the last k elements and a running sum. For each new value: add it to the sum and queue. If queue size > k, remove the oldest element from the front and subtract it from the sum. Return sum / min(count, k).

Example explanation

k = 3. Stream: [1, 10, 3, 5].

• Add 1: window=[1], sum=1. Avg = 1/1 = 1.0.
• Add 10: window=[1,10], sum=11. Avg = 11/2 = 5.5.
• Add 3: window=[1,10,3], sum=14. Avg = 14/3 = 4.67.
• Add 5: window=[10,3,5] (remove 1), sum=18. Avg = 18/3 = 6.0.

Common mistakes candidates make

• Recomputing the sum from scratch each time (O(k) per call vs O(1)).
• Not removing the oldest element when window exceeds size k.
• Integer division instead of float division for the average.
• Using a list with pop(0) instead of a deque (O(n) pop vs O(1)).

Interview preparation tip

Moving average is the canonical sliding window with running sum design problem. The key insight: maintain a running sum and update it incrementally (add new, subtract old) instead of recomputing from the window each time. Use collections.deque for O(1) append and popleft operations. This incremental update pattern applies to any "window aggregate" — running sum, running max (harder), running count. Practice all three for a complete sliding window skillset.