## Friday, February 19, 2016

### Buttercola: Moving average

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``;`
`        ``}`
`    ``}`