C++, circular array, keep running total design


  • 0
    • Use a circular array to scale with the follow up.
    • Keep a lastTimestamp and a running total of hits to avoid summing up all the hits every time we call getHits.
    • Check if delta is larger than 300, in which case hits and numHits need to be reset.
    class HitCounter {
    public:
        HitCounter() : hits_(300, 0), pos_(-1), lastTimestamp_(0), numHits_(0) {
        }
        
        void hit(int timestamp) {
            int delta = (timestamp - lastTimestamp_) % 300;
            if (timestamp - lastTimestamp_ >= 300) {
                hits_.assign(300, 0);
                pos_ = (pos_ + delta) % 300;
                hits_[pos_] = numHits_ = 1;
            }
            else {
                for (int i = 0; i < delta; i++) {
                    pos_ = (pos_ + 1) % 300;
                    numHits_ -= hits_[pos_];
                    hits_[pos_] = 0;
                }
                hits_[pos_]++;
                numHits_++;
            }
            lastTimestamp_ = timestamp;
        }
        
        int getHits(int timestamp) {
            int delta = (timestamp - lastTimestamp_) % 300;
            if (timestamp - lastTimestamp_ >= 300) {
            	pos_ = (pos_ + delta) % 300;
                numHits_ = 0;
                hits_.assign(300, 0);
            }
            else {
                for (int i = 0; i < delta; i++) {
                    pos_ = (pos_ + 1) % 300;
                    numHits_ -= hits_[pos_];
                    hits_[pos_] = 0;
                }
            }
            lastTimestamp_ = timestamp;
            return numHits_;
        }
    private:
        vector<int> hits_;
        int pos_;
        int lastTimestamp_;
        int numHits_;
    };
    

Log in to reply
 

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