Easy to understand C++ good for long interval frequent hit burst


  • 0
    F
    1. If hit is nearly evenly distributed throughout the window, this solution takes more space that the array-based solutions many others have posted here.
    2. If hit burst happens a lot and the window is very large, this solution saves much space.
    class HitCounter {
        struct Counter {
            int timestamp;
            int count;
            Counter(int ts) : timestamp(ts), count(1) {}
        };
        
        queue<Counter *> dq;
        unordered_map<int, Counter *> mp; // timestamp => *
        
    public:
        /** Initialize your data structure here. */
        HitCounter() {
            
        }
        
        /** Record a hit.
            @param timestamp - The current timestamp (in seconds granularity). */
        void hit(int timestamp) {
            if (mp.find(timestamp) == mp.end()) {
                mp[timestamp] = new Counter(timestamp);
                dq.push(mp[timestamp]);
            } else {
                mp[timestamp]->count++;
            }
        }
        
        /** Return the number of hits in the past 5 minutes.
            @param timestamp - The current timestamp (in seconds granularity). */
        int getHits(int timestamp) {
            while (!dq.empty() && dq.front()->timestamp+300 <= timestamp) {
                Counter *pc = dq.front();
                mp.erase(pc->timestamp);
                dq.pop();
            }
            int res = 0;
            for (auto &p : mp) {
                res += p.second->count;
            }
            return res;
        }
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.