346. Moving Average from Data Stream
Model: qwen2.5-coder:14b
Topics: Design,Queue
FAANG asked: 1
Acceptance rate: 73.6%
Problem Breakdown
The problem requires us to design a class MovingAverage that calculates the moving average of a stream of integers over a sliding window of a given size. The inputs are:
- An integer
sizerepresenting the window size. - A series of integers
valwhich are added to the stream one by one.
The output is:
- For each call to
next(val), return the moving average of the lastsizevalues in the stream.
Implicit constraints and edge cases include:
- The window size can be as small as 1 or as large as 1000.
- Values in the stream can range from -10^5 to 10^5.
- There can be up to 10^4 calls to
next.
Intuition
A brute-force approach would involve maintaining a list of all values and recalculating the average each time next is called. This would result in a time complexity of O(n) for each call, where n is the window size.
The key insight is to use a queue (FIFO structure) to efficiently manage the sliding window. By keeping track of the sum of the current window and updating it as new values are added or old ones are removed, we can achieve an average time complexity of O(1) for each call to next.
Approach
- Data Structure: Use a queue to store the last
sizeelements of the stream. - Initialization: Initialize the queue and keep track of the current sum of the window.
- Adding New Values:
- When a new value is added, append it to the queue and add its value to the current sum.
- If the queue exceeds the specified size, remove the oldest element from the queue and subtract its value from the current sum.
- Calculating the Average: The moving average is simply the current sum divided by the number of elements in the queue (which should not exceed
size).
Complexity Analysis
- Time Complexity: O(1) for each call to
next. Each element is added and removed from the queue at most once. - Space Complexity: O(size), where size is the window size. This is because we store up to
sizeelements in the queue.
Solution
from collections import deque
class MovingAverage:
def __init__(self, size: int):
self.size = size
self.queue = deque()
self.current_sum = 0.0
def next(self, val: int) -> float:
if len(self.queue) == self.size:
self.current_sum -= self.queue.popleft()
self.queue.append(val)
self.current_sum += val
return self.current_sum / len(self.queue)
# Example usage:
# movingAverage = MovingAverage(3)
# print(movingAverage.next(1)) # Output: 1.0
# print(movingAverage.next(10)) # Output: 5.5
# print(movingAverage.next(3)) # Output: 4.66667
# print(movingAverage.next(5)) # Output: 6.0
Edge Cases Handled
- Window Size of 1: The average is simply the last value added.
- Stream with fewer than
sizeelements: The average is calculated over all available elements. - Negative Values: The sum and average calculations handle negative values correctly.
- Large Values: The use of floating-point arithmetic ensures that large sums are handled without overflow.