346. Moving Average from Data Stream

Given a stream of integers and a window size, calculate the moving average of all integers in the sliding window.

Example:

MovingAverage m = new MovingAverage(3);
m.next(1) = 1
m.next(10) = (1 + 10) / 2
m.next(3) = (1 + 10 + 3) / 3
m.next(5) = (10 + 3 + 5) / 3

Thoughts:

1. with deque: trival
2. without deque: use ( i + 1) % as circular array

Code: with deque

class MovingAverage(object):

    def __init__(self, size):
        """
        Initialize your data structure here.
        :type size: int
        """
        self.queue = collections.deque(maxlen = size)

    def next(self, val):
        """
        :type val: int
        :rtype: float
        """

        self.queue.append(val)
        return float(sum(self.queue))/len(self.queue)



# Your MovingAverage object will be instantiated and called as such:
# obj = MovingAverage(size)
# param_1 = obj.next(val)

Code: without deque

class MovingAverage(object):

    def __init__(self, size):
        """
        Initialize your data structure here.
        :type size: int
        """
        self.w = [0] * size
        self.n = 0 
        self.i = 0
        self.size = size
        self.sum = 0

    def next(self, val):
        """
        :type val: int
        :rtype: float
        """
        if self.n < self.size: self.n +=1

        self.sum -= self.w[self.i]
        self.sum += val
        self.w[self.i] = val
        self.i = (self.i + 1) % self.size

        return float(sum(self.w))/self.n



# Your MovingAverage object will be instantiated and called as such:
# obj = MovingAverage(size)
# param_1 = obj.next(val)