Design Hit Counter(Medium)计数器

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.
思路: 要求保证时间顺序，可以用一个queue将每次点击的timestamp放入queue中。
getHits: 可以从queue的头开始看， 如果queue开头的时间在范围外，就poll掉。最后返回queue的size。

public class HitCounter {
    private ArrayDeque<Integer> queue;

    /** Initialize your data structure here. */
    public HitCounter() {
        queue = new ArrayDeque<Integer>();
    }

    /** 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) {
        int startTime = timestamp - 300;
        while(!queue.isEmpty() && queue.peek() <= startTime) {
            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);
 */

Follow up: 说如果每秒的点击次数真的是超多，那你该怎么设计呢？

加入1s内进来了1000个hits， 那么我们queue里面就有1000个timestamp，在调用getHits(301), 也就需要删除1000个timestamp， 这样严重影响性能。

比较巧的方法，我们可以用两个bucket来解决，分别用两个大小为300的一维数组，timestamps, hits,前者用来盛放timestamp， 后者用来盛放hit。

hit(int timestamp): 对timestamp 取余数，得到在数组中对应的坐标位置，再看坐标位置存的timestamp跟这个新的timestamp是否一样，如果不一样，则证明坐标位置存的timestamp已经过期了，把这个新的timestamp存入即可。

getHits(int timestamp): 遍历数组，把没过期的timestamp对应的hits加和

public class HitCounter {
    int hits[];
    int timestamps[];

    /** Initialize your data structure here. */
    public HitCounter() {
        hits = new int[300];
        timestamps = new int[300];
    }

    /** Record a hit.
        @param timestamp - The current timestamp (in seconds granularity). */
    public void hit(int timestamp) {
        int index = timestamp % 300;
        if (timestamps[index] != timestamp) {
            timestamps[index] = timestamp;
            hits[index] = 1;
        } else {
            hits[index]++;
        }
    }

    /** Return the number of hits in the past 5 minutes.
        @param timestamp - The current timestamp (in seconds granularity). */
    public int getHits(int timestamp) {
        int res = 0;
        for (int i = 0; i < 300; i++) {
            if(timestamp - timestamps[i] < 300) {
                res += hits[i];
            } 
        }
        return res;
    }
}