How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a Medium difficulty Coding & Algorithms question, commonly asked during Technical Screen rounds at Meta.

What role is this question designed for?

This question is commonly asked for Machine Learning Engineer candidates at Meta during technical interviews.

Implement sliding-window moving average

Company: Meta

Role: Machine Learning Engineer

Category: Coding & Algorithms

Difficulty: Medium

Interview Round: Technical Screen

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.

Quick Answer: This question evaluates a candidate's ability to implement an efficient streaming data structure and manage numerical precision and overflow when computing a 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

Input: (3, [1, 10, 3, 5])

Expected 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.

Input: (4, [])

Expected Output: []

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

Input: (1, [4, -2, 7])

Expected Output: [4.0, -2.0, 7.0]

Explanation: With window size 1, the moving average is always the most recent value.

Input: (5, [-1, -2, -3])

Expected Output: [-1.0, -1.5, -2.0]

Explanation: Fewer than k values have been seen, so each average is over all values seen so far: -1/1, -3/2, and -6/3.

Input: (2, [1000000000, 1000000000, 1])

Expected Output: [1000000000.0, 1000000000.0, 500000000.5]

Explanation: The first two averages are over [1000000000] and [1000000000, 1000000000]. After the third insertion, the window becomes [1000000000, 1], whose average is 1000000001 / 2 = 500000000.5.

Solution

def solution(k, values):
    from collections import deque

    if k <= 0:
        raise ValueError('k must be positive')

    window = deque()
    running_sum = 0
    averages = []

    for val in values:
        window.append(val)
        running_sum += val

        if len(window) > k:
            running_sum -= window.popleft()

        averages.append(running_sum / len(window))

    return averages

Time complexity: O(n) total for n incoming values, which is O(1) amortized per call to next. Space complexity: O(k).

Hints

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

Quick Overview

This question evaluates a candidate's ability to implement an efficient streaming data structure and manage numerical precision and overflow when computing a sliding-window moving average.