LC 0346 [E] Moving Average from Data Stream - ALawliet/algorithms GitHub Wiki

sliding window (deque with max size)

class MovingAverage(object):

    def __init__(self, size):
        self.dq = deque()
        self.maxlen = size
        self.total = 0

    def next(self, val):
        self.dq.append(val)
        if len(self.dq) > self.maxlen:
            self.total -= self.q.popleft()
        self.total += val
        return self.total / len(self.dq)

class MovingAverage(object):

    def __init__(self, size):
        self.dq = deque(maxlen=size) # maxlen will popleft() for us

    def next(self, val):
        self.dq.append(val)
        return sum(self.dq) / len(self.dq)

class MovingAverage:
    def __init__(self, size: int):
        self.size = size
        self.queue = deque()
        # number of elements seen so far
        self.window_sum = 0
        self.count = 0

    def next(self, val: int) -> float:
        # calculate the new sum by shifting the window
        self.queue.append(val)
        tail = self.queue.popleft() if len(self.queue) > self.size else 0

        self.window_sum = self.window_sum - tail + val

        return self.window_sum / len(self.queue)

class MovingAverage:
    def __init__(self, size: int):
        self.size = size
        self.queue = [0] * self.size
        self.head = self.window_sum = 0
        # number of elements seen so far
        self.count = 0

    def next(self, val: int) -> float:
        self.count += 1 # we need to track count because len(queue) is always size now
        # calculate the new sum by shifting the window
        tail = (self.head + 1) % self.size
        self.window_sum = self.window_sum - self.queue[tail] + val
        # move on to the next head
        self.head = (self.head + 1) % self.size
        self.queue[self.head] = val
        n = min(self.size, self.count) # n will either be the max size or not there yet
        print(self.size, self.count, n)
        return self.window_sum / n

class MyCircularQueue:

    def __init__(self, k: int):
        self.q = [0] * k
        self.headIndex = 0
        self.n = 0
        self.k = self.capacity = k
        

    def enQueue(self, value: int) -> bool:
        if self.n == self.k:
            self.deQueue()
        nextHeadIndex = (self.headIndex + self.n) % self.k
        self.q[nextHeadIndex] = value # set the value at next available spot
        self.n += 1
        return True
        

    def deQueue(self) -> bool:
        nextHeadIndex = (self.headIndex + 1) % self.k
        self.headIndex = nextHeadIndex # just move the head forward
        self.n -= 1
        return True
        

    def Front(self) -> int: # where is the current head?
        if not self.n:
            return -1
        return self.q[self.headIndex]
        

    def Rear(self) -> int: # where is the current tail?
        if not self.n:
            return -1
        tailIndex = (self.headIndex + self.n - 1) % self.k
        return self.q[tailIndex]
        

    def isEmpty(self) -> bool:
        return not self.n
        

    def isFull(self) -> bool:
        return self.n == self.k

class MovingAverage:
    def __init__(self, size: int):
        self.queue = MyCircularQueue(size)

    def next(self, val: int) -> float:
        self.queue.enQueue(val)
        return sum(self.queue.q) / self.queue.n

don't be dumb:

from collections import deque

size = 3
items = [1,2,3,4,5]

q = deque()
for i in items:
    runsum = q[-1] + i if q else i
    if len(q) + 1 > size:
        minus = q.popleft()
        print('popleft', runsum, minus)
        runsum -= minus # this is wrong because we decremented the old running sum
    q.append(runsum)
    print(q, runsum)

print('***')

q = deque()
cumsum = 0
for i in items:
    cumsum += i
    if len(q) == size:
        minus = q.popleft()
        print('popleft', cumsum, minus)
        cumsum -= minus # this is correct because we decremented the old value
    q.append(i)
    print(q, cumsum)

deque([1]) 1
deque([1, 3]) 3
deque([1, 3, 6]) 6
popleft 10 1
deque([3, 6, 9]) 9
popleft 14 3
deque([6, 9, 11]) 11
***
deque([1]) 1
deque([1, 2]) 3
deque([1, 2, 3]) 6
popleft 10 1
deque([2, 3, 4]) 9
popleft 14 2
deque([3, 4, 5]) 12