Simple C++ solution with a linked list (with explanation)


  • 0
    G

    We maintain a linked list of pairs. Each pair holds {timestamp, hits}. At max the length of this linked list will grow to 300, one for each second.
    For hit(), check the last node to see if we have to insert a new node if its a newer time stamp. Increment the hits on the last node.
    For getHits(), iterate the list discarding entries older than 5 min and summing up the hits for the remaining entries.

    This solution is scalable because the data structures do not grow in size with load.

    class HitCounter {
        list<pair<int, int>> my_list;   // list of {timestamp, hits}
    
    public:
        HitCounter() {}
    
        void hit(int timestamp) {
            if (my_list.empty() || my_list.back().first != timestamp) {
                pair<int, int> p(timestamp, 0);     // insert new node in the list
                my_list.push_back(p);
            }
            my_list.back().second++;
        }
    
        int getHits(int timestamp) {
            int cnt = 0;
            for (list<pair<int, int>>::iterator itr = my_list.begin(); itr != my_list.end();) {
                if (timestamp - itr->first >= 300) itr = my_list.erase(itr);    // discard entries older than 5 min
                else {
                    cnt += itr->second;
                    itr++;
                }
            }
            return cnt;
        }
    };
    

Log in to reply
 

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