293. Moving Average from Data Stream
Design a MovingAverage class that reports the running mean of the most recent values in a stream of integers.
The constructor receives size, the width of the sliding window. Every call to next(val) pushes one new integer from the stream and returns the average of the last size values — or of everything seen so far, while the stream is still shorter than the window.
Your class is driven by a scripted stream read from input. To keep the output exact, every average is printed with exactly 5 digits after the decimal point (the harness does the formatting — next just returns the number).
Example 1:
Input: MovingAverage(3); next(1), next(10), next(3), next(5)
Output: [1.00000, 5.50000, 4.66667, 6.00000]
Explanation: next(1) averages [1] → 1. next(10) averages [1, 10] → 5.5. next(3) averages [1, 10, 3] → 14/3 ≈ 4.66667. next(5) slides the window to [10, 3, 5] → 18/3 = 6.
Example 2:
Input: MovingAverage(1); next(4), next(-2), next(7)
Output: [4.00000, -2.00000, 7.00000]
Explanation: With a window of width 1, each average is just the newest value.
Constraints:
- 1 ≤ size ≤ 1000
- -10⁵ ≤ val ≤ 10⁵
- 1 ≤ number of next calls ≤ 10⁴
Hints:
Only the last size values ever matter. Which structure lets you add at one end and discard from the other in O(1)?
Keep a running sum alongside a queue: when the window is full, subtract the value that falls out and add the one that arrives — every next call becomes O(1).
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: MovingAverage(3); next(1), next(10), next(3), next(5)
Expected output: [1.00000, 5.50000, 4.66667, 6.00000]