C++ 0ms O(300) time and O(300) space handles large number of hits per second


  • 0
    S
    public:
        /** Initialize your data structure here. */
        HitCounter() {
            total = 0;
        }
        
        /** Record a hit.
            @param timestamp - The current timestamp (in seconds granularity). */
        void hit(int timestamp) {
            if(li.empty() || li.back().first != timestamp)
                li.push_back(make_pair(timestamp, 1));
            else
                ++li.back().second;
            ++total;
        }
        
        /** Return the number of hits in the past 5 minutes.
            @param timestamp - The current timestamp (in seconds granularity). */
        int getHits(int timestamp) {
            while(!li.empty() && timestamp - li.front().first >= 300) {
                total -= li.front().second;
                li.pop_front();
            }
            return total;
        }
    private:
        list<pair<int, int>> li;
        int total;
    };
    
    /**
     * Your HitCounter object will be instantiated and called as such:
     * HitCounter obj = new HitCounter();
     * obj.hit(timestamp);
     * int param_2 = obj.getHits(timestamp);
     */

Log in to reply
 

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