362. Design Hit Counter
Solution
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.
Example:
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);
Follow up:
What if the number of hits per second could be very large? Does your design scale?
Credits:
Special thanks to @elmirap for adding this problem and creating all test cases.
Solution
坑：注意同一时间可能会hit多次！
Queue, hit O(1), getHit O(n), S(n)
蛮有意思的一道题，计算5min之内的hit count。注意，题目说明了对于getHits和hit方法来说，他们的调用是按照时间顺序递增的，不会出现getHits(5)然后hit(4)的情况（反之亦然）。所以这道题并不是很复杂。
第一个思路就是用queue去做，queue里面存储当前所有的(timestamp, count) pairs，需要一个prev[]变量保存当前timestamp，当遇到更新的timestamp时就将prev入队列。这样做是因为queue没有getTail方法。。
getHits就比较tricky了。首先要将queue头部的老timestamp弹出，最重要的是还需要比较prev！因为prev还没有入队列。
这个解法的问题是，如果一直调用hit()，那么queue是会持续增长的，占用空间可能很大。其实解决起来也很简单，在hit中也evict old elements即可。
class HitCounter {
private Queue<int[]> queue; // store (timestamp, count)
private int[] prev;
private int count = 0;
/** Initialize your data structure here. */
public HitCounter() {
queue = new LinkedList<>();
}
/** Record a hit.
@param timestamp - The current timestamp (in seconds granularity). */
public void hit(int timestamp) {
if (prev != null) {
if (prev[0] < timestamp) {
queue.offer(prev);
prev = new int[] {timestamp, 0};
}
++prev[1];
} else {
prev = new int[] {timestamp, 1};
}
++count;
}
/** Return the number of hits in the past 5 minutes.
@param timestamp - The current timestamp (in seconds granularity). */
public int getHits(int timestamp) {
while (!queue.isEmpty() && timestamp - queue.peek()[0] >= 300) {
count -= queue.poll()[1];
}
// don't forget to compare with prev! prev is not in the queue yet
if (prev != null && timestamp - prev[0] >= 300) {
count -= prev[1];
prev = null;
}
return count;
}
}
/**
* Your HitCounter object will be instantiated and called as such:
* HitCounter obj = new HitCounter();
* obj.hit(timestamp);
* int param_2 = obj.getHits(timestamp);
*/
Queue, hit O(1), getHit O(n), S(n)
其实用不着prev那么麻烦，直接将每个timestamp进队列即可...不过这样做比较浪费空间。
class HitCounter {
private Queue<Integer> queue;
/** Initialize your data structure here. */
public HitCounter() {
queue = new LinkedList<>();
}
/** Record a hit.
@param timestamp - The current timestamp (in seconds granularity). */
public void hit(int timestamp) {
queue.offer(timestamp);
}
/** Return the number of hits in the past 5 minutes.
@param timestamp - The current timestamp (in seconds granularity). */
public int getHits(int timestamp) {
while (!queue.isEmpty() && timestamp - queue.peek() >= 300) {
queue.poll();
}
return queue.size();
}
}
/**
* Your HitCounter object will be instantiated and called as such:
* HitCounter obj = new HitCounter();
* obj.hit(timestamp);
* int param_2 = obj.getHits(timestamp);
*/
TreeMap, hit O(1), getHits O(n), S(n)
TreeMap不仅可以实现O(1)的get(key)，而且还能保证插入顺序，这样iterate的时候是按照插入顺序遍历的，我们就可以把老的timestamp移出了。
这个做法其实跟上面第二个Queue实现原理一样。
class HitCounter {
private TreeMap<Integer, Integer> window;
private int count;
/** Initialize your data structure here. */
public HitCounter() {
window = new TreeMap<>();
}
/** Record a hit.
@param timestamp - The current timestamp (in seconds granularity). */
public void hit(int timestamp) {
window.put(timestamp, window.getOrDefault(timestamp, 0) + 1);
++count;
}
/** Return the number of hits in the past 5 minutes.
@param timestamp - The current timestamp (in seconds granularity). */
public int getHits(int timestamp) {
Iterator<Map.Entry<Integer, Integer>> iter
= window.entrySet().iterator();
while (iter.hasNext()) {
Map.Entry<Integer, Integer> entry = iter.next();
if (timestamp - entry.getKey() < 300) {
break;
}
count -= entry.getValue();
iter.remove();
}
return count;
}
}
/**
* Your HitCounter object will be instantiated and called as such:
* HitCounter obj = new HitCounter();
* obj.hit(timestamp);
* int param_2 = obj.getHits(timestamp);
*/
Circular array, hit O(1), getHits O(1), S(1)
Basic ideal is using buckets. 1 bucket for every second because we only need to keep the recent hits info for 300 seconds. hit[] array is wrapped around by mod operation. Each hit bucket is associated with times[] bucket which record current time. If it is not current time, it means it is 300s or 600s... ago and need to reset to 1.
这个解法目前来看时间空间都是最优的。
class HitCounter {
private int[] timestamps;
private int[] counts;
/** Initialize your data structure here. */
public HitCounter() {
timestamps = new int[300];
counts = new int[300];
}
/** Record a hit.
@param timestamp - The current timestamp (in seconds granularity). */
public void hit(int timestamp) {
int index = timestamp % 300; // tricky
if (timestamps[index] == timestamp) {
++counts[index];
} else {
timestamps[index] = timestamp; // the old timestamp should be evicted
counts[index] = 1;
}
}
/** Return the number of hits in the past 5 minutes.
@param timestamp - The current timestamp (in seconds granularity). */
public int getHits(int timestamp) {
int hits = 0;
// iterate array
for (int i = 0; i < 300; ++i) {
if (timestamp - timestamps[i] < 300) {
hits += counts[i];
}
}
return hits;
}
}
/**
* Your HitCounter object will be instantiated and called as such:
* HitCounter obj = new HitCounter();
* obj.hit(timestamp);
* int param_2 = obj.getHits(timestamp);
*/
