A C++ rotational window solution


  • 0
    A
    class HitCounter {
    private:
        vector<int> buckets;
        int i, lastTimestamp, total;
    public:
        /** Initialize your data structure here. */
        HitCounter() {
            buckets = vector<int>(300, 0);
            i = total = 0;
            lastTimestamp = 0;
        }
        
        void rotate(int timestamp) {
            int diff = timestamp - lastTimestamp;
            lastTimestamp = timestamp;
            if (diff < 300) {
                while (diff--) {
                    i = (i == 299) ? 0 : i + 1;
                    total -= buckets[i];
                    buckets[i] = 0;
                }
            }
            else {
                buckets.assign(300, 0);
                i = total = 0;
            }
        }
        
        /** Record a hit.
            @param timestamp - The current timestamp (in seconds granularity). */
        void hit(int timestamp) {
            rotate(timestamp);
            ++buckets[i], ++total;
        }
        
        /** Return the number of hits in the past 5 minutes.
            @param timestamp - The current timestamp (in seconds granularity). */
        int getHits(int timestamp) {
            rotate(timestamp);
            return total;
        }
    };

Log in to reply
 

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