362. Design Hit Counter

https://leetcode.com/problems/design-hit-counter/

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?

实现点击记录api，hit(ts)代表在ts （单位s）时刻有一次点击，getHits(ts)返回ts前五分钟内的点击数，每次调用的ts只会递增或不变。由于ts不会降低，因此只保留当前ts内五分钟的记录即可。分出300个bucket代表一轮五分钟内对应的秒所记录的count。每个bucket还额外存count对应的ts，当当前ts与记录的ts不符合时意味着已经进入到新一轮的300s，count清0。

参考自这。

class HitCounter {
public:
    vector<vector<int>> freq;
    /** Initialize your data structure here. */
    HitCounter() {
        freq = vector<vector<int>>(300, vector<int>(2, 0));
    }
    
    /** Record a hit.
        @param timestamp - The current timestamp (in seconds granularity). */
    void hit(int timestamp) {
        const auto i = timestamp % 300;
        if (freq[i][0] != timestamp) {
            freq[i][0] = timestamp;
            freq[i][1] = 0;
        }
        ++freq[i][1]; 
    }
    
    /** Return the number of hits in the past 5 minutes.
        @param timestamp - The current timestamp (in seconds granularity). */
    int getHits(int timestamp) {
        int res = 0;
        for (const auto &f : freq) {
            if (timestamp - f[0] < 300) res += f[1];
        }
        return res;
    }
};

/**
 * Your HitCounter object will be instantiated and called as such:
 * HitCounter* obj = new HitCounter();
 * obj->hit(timestamp);
 * int param_2 = obj->getHits(timestamp);
 */