Problem Statement

You are tasked with designing a system that counts the number of hits received in the past 5 minutes (i.e., the last 300 seconds).

Implement a class HitCounter with the following methods:

• void hit(int timestamp)
  • Records a hit at the given timestamp (in seconds).
  • You may assume that timestamps for hit calls are given in monotonically increasing order (i.e., each timestamp is equal to or greater than the previous one).
• int get(int timestamp)
  • Returns the numbers of hits received in the past 5 minutes (i.e., from timestamp - 299 to timestamp, inclusive).
  • Also assumes timestamp values passed to get() are monotonically increasing.

Examples

Example 1:

HitCounter counter;

// Recording hits
counter.hit(1);
counter.hit(2);
counter.hit(3);

// Getting hits
counter.get(4);     // returns 3 (hits at 1, 2, 3 are within [4 - 299, 4])

counter.hit(300);

counter.get(300);   // returns 4 (hits at 1, 2, 3, 300 are within [1, 300])
counter.get(301);   // returns 3 (hit at 1 is now outside the 5-minute window)

Different Approaches

1️⃣ Queue data structure

Intuition:

Use a queue to store the timestamps. When a hit arrives:

• Push it to the queue.
• When get() is called, remove timestamps older than timestamp - 300.

Code:

#include <iostream>
#include <queue>

class HitCounter {
private:
    std::queue<int> hits;

public:
    // Record a hit at the given timestamp
    void hit(int timestamp) {
        hits.push(timestamp);
    }

    // Return number of hits in the past 5 minutes
    int get(int timestamp) {
        // Remove hits older than 5 minutes (300 seconds)
        while (!hits.empty() && hits.front() <= timestamp - 300) {
            hits.pop();
        }
        return hits.size();
    }
};

Usage:

int main() {
    HitCounter counter;

    counter.hit(1);
    counter.hit(2);
    counter.hit(3);
    
    std::cout << "Hits at timestamp 4: " << counter.get(4) << std::endl;  // Output: 3

    counter.hit(300);
    std::cout << "Hits at timestamp 300: " << counter.get(300) << std::endl; // Output: 4

    std::cout << "Hits at timestamp 301: " << counter.get(301) << std::endl; // Output: 3

    return 0;
}