Moving Average Over a Data Stream
Problem statement
Implement moving_average(k, values) to return the average of the latest k observations after each arrival. Before the window fills, average only the values seen so far.
- Implement the simple-average adapter below. Return one float per observation, using the number currently present as the divisor during warm-up. Empty input returns an empty list. Describe how the same state supports a streaming
next(value)method. - Implement a separate streaming variant whose current window, ordered from oldest to newest, assigns weights $1,2,\ldots,m$ to its $m$ values. Support constant-time updates without retaining the full stream. This follow-up does not change the adapter's output.
def moving_average(k: int, values: list) -> list[float]:
...
Constraints
kis a positive integer; inputs are finite numeric values.- Window storage must be $O(k)$, excluding the required output list.
- Each arrival must take $O(1)$ time.
Examples
moving_average(3, [1, 10, 3, 5]) -> [1.0, 5.5, 4.666666666666667, 6.0].moving_average(5, [1, 2]) -> [1.0, 1.5].moving_average(2, []) -> [].
For the weighted follow-up, the final window in the first example is [10, 3, 5]; specify the weighted result and the update invariant.
Show hint
What information changes between neighboring windows?
Relevant roles: ML Engineer, MLOps Engineer, Forward Deployed Engineer and AI Engineer.