MovingAverageFromDataStream346.java

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


public class MovingAverageFromDataStream346 {
    class MovingAverage {
        private int size;
        private Queue<Integer> cache;
        private long sum;
        
        /** Initialize your data structure here. */
        public MovingAverage(int size) {
            this.size = size;
            this.cache = new LinkedList<Integer>();
            this.sum = 0L;
        }
      
        public double next(int val) {
            if (this.cache.size() >= this.size) {
                this.sum -= this.cache.remove();
            }
            this.sum += val;
            this.cache.add(val);
            return this.sum * 1.0 / this.cache.size();
        }
    }


    class MovingAverage2 {
        private int[] window;
        private int head = 0;
        private int len = 0 ;
        private int sum = 0;

        /** Initialize your data structure here. */
        public MovingAverage2(int size) {
            this.window = new int[size + 1];
        }

        public double next(int val) {
            int nextPos = (this.head + this.len + 1) % this.window.length;
            this.window[nextPos] = val;
            this.len++;
            this.sum += val;
            
            if (this.len == this.window.length) {
                this.head++;
                this.head %= this.window.length;
                this.len--;
                this.sum -= this.window[this.head];
            }
            return this.sum * 1.0 / this.len;
        }
    }

}

/**
* Your MovingAverage object will be instantiated and called as such:
* MovingAverage obj = new MovingAverage(size);
* double param_1 = obj.next(val);
*/