[LintCode] Problem 642 - Moving Average from Data Stream

Posted on | In ,

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 // 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

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
private Queue<Integer> queue;
private double sum;
private int size;

public MovingAverage(int size) {
    queue = new LinkedList<>();
    sum = 0;
    this.size = size;
}

public double next(int val) {
    sum += val;

    if (queue.size() == size)
        sum -= queue.poll();

    queue.offer(val);
    return sum / queue.size();
}