Sliding Window Average from Data Stream
Given a stream of integers and a window size, calculate the moving average of all integers in the sliding window.
Have you met this question in a real interview?
Yes
Example
MovingAverage m = new MovingAverage(3);
m.next(1) = 1 // return 1.00000
m.next(10) = (1 + 10) / 2 // return 5.50000
m.next(3) = (1 + 10 + 3) / 3 // return 4.66667
m.next(5) = (10 + 3 + 5) / 3 // return 6.00000
from collections import deque
#thinking process
#because the element is coming one after another, so when the size + 1's number coming in, we need to remove the first coming number from the window and calculate the avg
#so a queue can be used here to ensure the first in first out
#keep a queue size <= k, if greater than k then pop and substract the value that poped out and add the number that come in and calculate the avg
class MovingAverage:
"""
@param: size: An integer
"""
def __init__(self, size):
# do intialization if necessary
self.que = deque([])
self.size = size
self.total = 0.0
"""
@param: val: An integer
@return:
"""
def next(self, val):
# write your code here
if len(self.que) < self.size:
self.total += val
self.que.appendleft(val)
else:
self.total -= self.que.pop()
self.que.appendleft(val)
self.total += val
return self.total / len(self.que)
# Your MovingAverage object will be instantiated and called as such:
# obj = MovingAverage(size)
# param = obj.next(val)