Design hit counter

XXX. Design Hit Counter

Queue

Design

Problem Statement:

Design a hit counter that counts the number of hits received in the past 5 minutes (300 seconds). Implement the following methods:

• hit(int timestamp): Records a hit at the given timestamp (in seconds granularity).
• getHits(int timestamp): Returns the number of hits in the past 5 minutes from the given timestamp.

Assume that calls to hit and getHits are made in non-decreasing order of timestamp.

Algorithm:

The solution uses a queue to efficiently track the timestamps of hits:

1. Maintain a queue of timestamps, where each timestamp represents a recorded hit.
2. For the hit method:
   • Add the timestamp to the queue.
3. For the getHits method:
   • Remove timestamps from the front of the queue that are older than 5 minutes (300 seconds) relative to the current timestamp.
   • Return the size of the queue, which represents the number of hits in the past 5 minutes.

Complexity:

Time Complexity:

• hit: O(1), as adding an element to the queue takes constant time.
• getHits: O(n), where n is the number of timestamps in the queue. In the worst case, all timestamps are removed.

Space Complexity: O(n), where n is the number of hits recorded in the past 5 minutes.

Java Implementation:

public class HitCounter {
    
    Queue q;

    /** Initialize your data structure here. */
    public HitCounter() {
        q = new LinkedList<>();
    }
    
    /** Record a hit.
        @param timestamp - The current timestamp (in seconds granularity). */
    public void hit(int timestamp) {
        q.offer(timestamp);
    }
    
    /** Return the number of hits in the past 5 minutes.
        @param timestamp - The current timestamp (in seconds granularity). */
    public int getHits(int timestamp) {
        
        while (q.size() > 0 && timestamp - q.peek() >= 300) 
            q.poll();
        
        return q.size();
    }
}