Sunday, February 14, 2016

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. 

Code (Java):
import java.util.*;

public class Solution {
    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;
        }
    }
}

Follow-up:

How to save more space? 

Solution:
Use a circular buffer. 

Code (Java):
import java.util.*;

public class Solution {
    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;
    }
    
    public static void main(String[] args) throws InterruptedException {
        Solution sol = new Solution();
        sol.record(1);
        sol.record(2);
        sol.record(3);
        sol.record(4);
        
        Thread.sleep(1000);
        
        System.out.println(sol.getAvg());
    }
    
    class Event {
        long prevTime;
        long hits;
        long sum;
        
        public Event() {
            prevTime = 0;
            hits = 0;
            sum = 0;
        }
    }
}


2 comments:

  1. You could optimize your second solution by doing getAvg() more efficiently. Using 2 field variables, totalSum and totalHits. In doing record(), if currTime == event.prevTime then increment totalSum and add up val to totalVal. Otherwise subtract totalVal by the val in old event, and totalHits by old hits.

    ReplyDelete
    Replies
    1. I think we should also consider that , when calling getAvg() , we need to rule out those expired. Although we can track the totalSum, we still need to traverse the events[] to subtract the expired ones, which is the same as the for loop adding up the valid ones.

      Delete