Given a stream of input, and a API int getNow() to get the current time stamp, Finish two methods:

1. void record(int val) to save the record.

2. double getAvg() to calculate the averaged value of all the records in 5 minutes.

Solution:

Maintain a sliding window (queue) which stores the elements in 5 minutes. Also maintain the sum of

the records in the window.

For the record(), add an event into the queue. Remove all expired events from the queue.

For the getAvg(), first remove the expired events from the queue, and then calculate the average.

/**
 * Created by 1000132937 on 3/25/2018.
 */
import java.util.Queue;
import java.util.LinkedList;

public class MovingAverage {
    private static int timeWindow = 5;
    private int sum = 0;
    private Queue<Event> queue = new LinkedList<Event>();

    static class Event{
        int time;
        int val;
        public Event(int time, int val){
            this.time = time;
            this.val = val;
        }
    }

    public double getAvg() {
        removeExpiredRecords();
        if(queue.isEmpty()) {
            return 0;
        } else {
            return (double) sum / queue.size();
        }
    }

    private int getNow() {
        return (int) Math.floor(System.currentTimeMillis()/60000);
    }
    private void removeExpiredRecords() {
        while(!queue.isEmpty() && expired(getNow(), queue.peek().time)) {
            Event cur = queue.poll();
            sum -= cur.val;
        }
    }

    private void record(int val) {
        Event event = new Event(getNow(), val);
        queue.offer(event);
        sum += val;
        removeExpiredRecords();
    }


    private boolean expired(int curTime, int prevTime){
        return curTime - prevTime > timeWindow;
    }
}