Moving Average Over a Data Stream

Reported in interviews at Atlassian Block (Square) Meta Millennium Management

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.

  1. 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.
  2. 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

  • k is 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.

Related free problems