Moving Average from Data Stream
Easy · Stack & Strings · Array · Design · Queue · Data Stream
Problem
Given a stream of integers, report the average of the most recent values inside a fixed-size window.
Implement MovingAverage:
- MovingAverage(size) sets the window size.
- next(val) adds val to the stream and returns the average of the last size values, or of all values so far if fewer than size have arrived.
The calls are given as ops (method names, the first being the constructor) and args (each call’s arguments); return every call’s result in order (None for the constructor). Answers within 10^-5 of the true value are accepted.
Examples
Input: ops = ["MovingAverage","next","next","next","next"], args = [[2],[4],[8],[3],[-1]] Output: [None, 4.0, 6.0, 5.5, 1.0]
With a window of 2, the last answer averages 3 and -1.
Input: ops = ["MovingAverage","next","next","next"], args = [[3],[1],[2],[4]] Output: [None, 1.0, 1.5, 2.3333333333333335]
Fewer than 3 values arrive, so each answer averages everything so far; the last is 7 / 3.
Input: ops = ["MovingAverage","next","next"], args = [[1],[-5],[9]] Output: [None, -5.0, 9.0]
A window of 1 always returns the newest value.
Constraints
- 1 <= size <= 1000
- -10^5 <= val <= 10^5
- At most 10^4 calls are made to next
Approaches
- Store everything, re-add the window each call — time O(size) per call, space O(number of calls)
Follow-up
What if the window is defined by time (the average of the values from the last w seconds) instead of a count? The queue holds (time, value) pairs and each call pops from the front every pair that has grown too old, so the window size changes from call to call but each pair still enters and leaves once.
Related problems
Start free on Cariara · Coding problems · System design studio
