Lesson 19 of 27
In Progress

Hit Counter

August 5, 2020

Design a hit counter which counts the number of hits received in the past 5 minutes.

Each function accepts a timestamp parameter (in seconds granularity) and you may assume that calls are being made to the system in chronological order (ie, the timestamp is monotonically increasing). You may assume that the earliest timestamp starts at 1.

It is possible that several hits arrive roughly at the same time.

Intput:
hit(1)
hit(2)
hit(3)
getHits(4)
hit(300)
getHits(300)
getHits(301)
Output: 
3
4
3

Explanation:
HitCounter counter = new HitCounter();

// hit at timestamp 1. 
counter.hit(1); 

// hit at timestamp 2. 
counter.hit(2);

 // hit at timestamp 3. 
counter.hit(3); 

// get hits at timestamp 4, should return 3. 
counter.getHits(4); 

// hit at timestamp 300. 
counter.hit(300);

 // get hits at timestamp 300, should return 4. 
counter.getHits(300); 

// get hits at timestamp 301, should return 3. 
counter.getHits(301);
import java.util.HashMap;
import java.util.LinkedList;
import java.util.Map;
import java.util.Queue;
public class TimeHitCounter {
public static void main(String[] args) {
TimeHitCounter counter = new TimeHitCounter();
System.out.println("hit(1)");
counter.hit(1);
System.out.println("hit(2)");
counter.hit(2);
System.out.println("hit(3)");
counter.hit(3);
System.out.println("getHits(4) : " + counter.getHits(4));
System.out.println("hit(300)");
counter.hit(300);
System.out.println("getHits(300) : " + counter.getHits(300));
System.out.println("getHits(301) : " + counter.getHits(301));
}
private static int timeWindow;
// Queue will only have timestamps which are unique and no duplicates
private Queue<Integer> queue;
// map will store timestamp and total of hits encountered at that time
private Map<Integer, Integer> timestampHitCountMap;
public TimeHitCounter() {
timeWindow = 60 * 5; // 60 seconds * 5 minutes
queue = new LinkedList<>();
timestampHitCountMap = new HashMap<>();
}
void hit(int timestamp) {
if (timestampHitCountMap.containsKey(timestamp)) {
// if the hit is already in the map just update the counter no need to add in queue
timestampHitCountMap.put(timestamp, timestampHitCountMap.get(timestamp) + 1);
} else { // if it is new hit remove expired hits from map and add the new hit timestamp to queue and map
removeExpiredHits(timestamp);
queue.add(timestamp);
timestampHitCountMap.put(timestamp, 1);
}
}
/**
* Return the number of hits in the past 5 minutes.
*/
int getHits(int timestamp) {
// cleanup old hits
removeExpiredHits(timestamp);
int totalHits = 0;
// sum all the values from the timestampHitCountMap
for (int counts : timestampHitCountMap.values()) {
totalHits = totalHits + counts;
}
return totalHits;
}
// Remove all hits that are too old.
private void removeExpiredHits(int currTimeStamp) {
// validate against the peek of the queue and delete all hits older than peek
while (!queue.isEmpty() && queue.peek() <= currTimeStamp - timeWindow) {
// remove the oldest hit whose timestamp is less than timeWindow
timestampHitCountMap.remove(queue.poll());
}
}
}

Question Source: LeetCode-362