Design Hit Counter - Leetcode Solution

The problem description for the 'Design Hit Counter' states:

"Design a hit counter which counts the number of hits received in the past 5 minutes."

"The function hit() will be called with a timestamp (in seconds granularity) each time a hit is generated."

"The function getHits() will be called with a timestamp (in seconds granularity) and should return the number of hits received in the past 5 minutes (300 seconds) excluding the hits generated at the timestamp exact same as the passed timestamp."

"Example: HitCounter counter = new HitCounter(); // hit at timestamp 1. counter.hit(1); // hit at timestamp 2. counter.hit(2); // hit at timestamp 3. counter.hit(3); // get hits at timestamp 4, should return 3. counter.getHits(4); // hit at timestamp 300. counter.hit(300); // get hits at timestamp 300, should return 4. counter.getHits(300); // get hits at timestamp 301, should return 3. counter.getHits(301);"

Solution: To solve this problem, we can use an array of size 300 to store the hits of the past 300 seconds. Each time the hit() function is called, we will update the value of the corresponding index in the array by 1.

But there is a special condition in this problem. If there are multiple hits at the same second, then we need to store the hit count of that second instead of just incrementing by 1.

So, instead of using an array of integers, we can use an array of pairs where each pair will store the count of hits and the second at which the hits occurred.

We can get the total number of hits in the past 5 minutes using a loop that goes through the array and checks if the second at that index is within the past 5 minutes. If it is, we add the count of hits at that position to our total hit count.

We also need to remove the hits that are older than 5 minutes to ensure that our array doesn't become too large. We can do this by checking if the second value of the first element in the array is older than 5 minutes. If it is, we remove that element and repeat until it's no longer older than 5 minutes.

Here is the code implementation for the above solution:

class HitCounter { private: vector<pair<int, int>> hits; public: /** Initialize your data structure here. */ HitCounter() {

}

/** Record a hit.
    @param timestamp - The current timestamp (in seconds granularity). */
void hit(int timestamp) {
    if(hits.empty() || hits.back().second != timestamp) {
        hits.push_back(make_pair(1, timestamp));
    } else {
        hits.back().first++;
    }
}

/** Return the number of hits in the past 5 minutes.
    @param timestamp - The current timestamp (in seconds granularity). */
int getHits(int timestamp) {
    int total = 0;
    int i = 0;
    while(i < hits.size()) {
        if(timestamp - hits[i].second >= 300) {
            hits.erase(hits.begin() + i);
        } else {
            total += hits[i].first;
            i++;
        }
    }
    return total;
}

};

With this implementation, we can now create a new HitCounter object and use the hit() and getHits() functions to count the hits and retrieve the hit count in the past 5 minutes.

1