Buttercola: Moving average
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.
How to save more space?
Solution:
Use a circular buffer.
Read full article from Buttercola: Moving average
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.
private Queue<Event> queue = new LinkedList<>(); private int sum = 0; // record an event public void record(int val) { Event event = new Event(getNow(), val); queue.offer(event); sum += event.val; removeExpiredRecords(); } private void removeExpiredRecords() { while (!queue.isEmpty() && expired(getNow(), queue.peek().time)) { Event curr = queue.poll(); sum -= curr.val; } } private double getAvg() { double average = 0; removeExpiredRecords(); if (queue.isEmpty()) { return 0; } else { return (double) sum / queue.size(); } } private boolean expired(int currTime, int prevTime) { return currTime - prevTime > 5; } class Event { int time; int val; public Event (int time, int val) { this.time = time; this.val = val; } }How to save more space?
Solution:
Use a circular buffer.
private Event[] events; public Solution() { events = new Event[300]; for (int i = 0; i < 300; i++) { events[i] = new Event(); } } public long getNow() { Date date = new Date(); return date.getTime() / 1000; } public void record(int val) { long currTime = getNow(); Event event = events[(int) currTime % 300]; // If the curr time happend the same sec as the prev time if (currTime == event.prevTime) { event.hits++; event.sum += val; event.prevTime = currTime; } else { event.hits = 1; event.sum = val; event.prevTime = currTime; } } public double getAvg() { int totalHits = 0; int totalSum = 0; long currTime = getNow(); for (Event event : events) { if (currTime - event.prevTime < 300) { totalHits += event.hits; totalSum += event.sum; } } return (double) totalSum / totalHits; } class Event { long prevTime; long hits; long sum; public Event() { prevTime = 0; hits = 0; sum = 0; } }