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.

For 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

The Idea: Using a queue is a great way of maintaining top k most current values since evicting the front of the queue means evicting the oldest element of the queue.

Complexity: O(K) space, O(1) time.

class MovingAverage {
public:
    MovingAverage(int size) : window(size) {
        cur_sum = 0;
        count = 0;
    };

    double next(int val)
    {
        if (count < window) {
            return next_init(val);
        }
        else {
            cur_sum -= q.front();
            q.pop();

            q.push(val);
            cur_sum += val;

            return cur_sum / window;
        }
    }


private:
    queue<int> q;

    unsigned count;
    double cur_sum;
    int window;

    double next_init(int val)
    {
        q.push(val);
        cur_sum += val;

        return cur_sum / ++count;
    }
};

Python Solution

import queue


class MovingAverage:
    def __init__(self, size):
        self.q = queue.Queue()
        self.cur_sum = 0
        self.window = size

    def next(self, val):
        if self.q.qsize() == self.window:
            old = self.q.get()
            self.cur_sum -= old

        self.q.put(val)
        self.cur_sum += val
        return self.cur_sum / self.q.qsize()