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.
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.
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.
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.
Community answers
Answer by RohitChandra
Please fix the question. Is it "achieve O(N)"??
Answer by RohitChandra
Solution:
from collections import deque
class MovingAverage:
def init(self, k: int):
if k <= 0:
raise ValueError("Window size k must be positive")
self.k = k
self.window = deque()
self.total = 0.0
def next(self, val: float) -> float:
self.window.append(val)
self.total += val
if len(self.window) > self.k:
removed = self.window.popleft()
self.total -= removed
return self.total / len(self.window)
TC:
For each call to next(val):
Append new value: O(1)
Remove old value if needed: O(1)
Update sum: O(1)
Compute average: O(1)
So the time complexity is: O(1) amortized per call
SC:
The queue stores at most k values. --> O(k)