Implement sliding-window moving average

Design a class MovingAverage that supports a constructor MovingAverage(k) and a method next(val) returning the average of the last k values from a data stream (or all seen values if fewer than k). Achieve O(1) amortized time per call and O(k) space. Explain your data structures, how you handle precision/overflow, and how you would test edge cases.

Implement Sliding-Window Moving Average

Design a moving average over a data stream. A class MovingAverage(k) would support a constructor with window size k and a method next(val) that inserts val and returns the average of the last k values, or all values seen so far if fewer than k have arrived.

For this coding challenge, implement a function solution(k, values) where values is the sequence of numbers passed to next. Return a list containing the result of each next call in order.

Your algorithm should use O(1) amortized time per inserted value and O(k) extra space. A good design keeps a queue of the current window and a running sum. Return floating-point averages. In Python, the running sum will not overflow because integers are unbounded; in fixed-width languages, use a 64-bit integer or larger for the sum before dividing.

Constraints

• 1 <= k <= 100000
• 0 <= len(values) <= 200000
• -1000000000 <= values[i] <= 1000000000

Examples

Example 1

Input: (3, [1, 10, 3, 5])
Output: [1.0, 5.5, 4.666666666666667, 6.0]

Explanation: The averages after each insertion are: [1]/1 = 1.0, [1,10]/2 = 5.5, [1,10,3]/3 = 14/3, and then the window slides to [10,3,5] with average 18/3 = 6.0.

Example 2

Input: (4, [])
Output: []

Explanation: No values are inserted, so there are no next calls and the result is an empty list.

Hints

1. Keep the sum of the current window so you do not need to recompute it from scratch after every insertion.
2. When the window grows beyond size k, remove the oldest value and subtract it from the running sum.