Understanding Design Hit Counter in Java

Introduction & Problem Explanation

A Hit Counter is a system that monitors and records the frequency of requests (hits) over a sliding temporal window—typically the last 5 minutes (or 300 seconds). It is widely used in rate limiting, web analytics, and security logging systems.

Our system must implement the following operations:

• hit(timestamp): Record a request event occurring at a given second-level timestamp (measured in seconds).
• getHits(timestamp): Return the total count of hits received in the past 5 minutes (i.e., within the range [timestamp - 299, timestamp]).

The primary design constraints are execution speed and memory efficiency. We can achieve this with a Queue data structure to store timestamps sequentially, allowing us to easily append hits at the end and trim stale events from the front.

The Algorithmic Approach

The Queue-Based Solution (Amortized O(1) Time, O(N) Space)

Since timestamps of incoming hits are monotonically increasing, we can log each hit into a Queue:

• Recording Hits: When hit(timestamp) is called, we append the timestamp to the queue. This is a simple O(1) insertion.
• Cleaning Stale Hits: When getHits(timestamp) is called, we must evict all logged timestamps that are older than 300 seconds. We check the head of the queue (queue.peek()) in a loop:
  If (timestamp - queue.peek() >= 300), the hit occurred outside the 5-minute window. We remove it (queue.poll()) and check the next head.
• Returning Count: We repeat this until the queue is empty or the oldest hit is within the 300-second window. The current size of the queue is the count of active hits.
• Time Complexity: Although getHits contains a loop, each hit is offered exactly once and polled at most once. Thus, the time complexity averages out to amortized O(1) per operation.

Step-by-Step Execution Walkthrough

Let's trace a Hit Counter receiving hits at timestamps 1, 2, and 3:

1. Step 1 (Record Hits):
   • hit(1): Queue becomes [1].
   • hit(2): Queue becomes [1, 2].
   • hit(3): Queue becomes [1, 2, 3].
2. Step 2 (getHits(4)):
   • Compare front of queue 1 with current time 4.
   • 4 - 1 = 3 (less than 300). No hits are stale.
   • Return queue size: 3.
3. Step 3 (getHits(300)):
   • Compare front of queue 1 with current time 300.
   • 300 - 1 = 299 (less than 300). No hits are stale.
   • Return queue size: 3.
4. Step 4 (getHits(301)):
   • Compare front of queue 1 with current time 301.
   • 301 - 1 = 300 (equal to or greater than 300). Stale! Remove 1. Queue becomes [2, 3].
   • Compare next front 2 with current time 301.
   • 301 - 2 = 299 (less than 300). Not stale. Stop loop.
   • Return queue size: 2.

Key Code Snippets & Explanations

Here is why the main logic in the solution is important:

• queue.offer(timestamp): Adds the incoming timestamp to the queue. It maintains the chronological ordering since timestamps are guaranteed to arrive in non-decreasing order.
• while (!queue.isEmpty() && timestamp - queue.peek() >= 300): The pruning loop. It checks the oldest element at the front and discards it if it has aged past 300 seconds.
• queue.size(): Returns the remaining active hits in the rolling 5-minute window in constant time.

Java Implementation Code

Below is the complete, self-contained Java source code that solves this problem. It also includes a main method that traces the execution with console outputs.

package io.practise.dsa;

import java.util.*;

public class DesignHitCounter {

    public static class HitCounter {
        // Queue to store the timestamps of incoming hits in chronological order
        private final Queue<Integer> queue;

        public HitCounter() {
            this.queue = new LinkedList<>();
        }

        // Record a hit at the given timestamp
        public void hit(int timestamp) {
            queue.offer(timestamp);
        }

        // Return the number of hits in the last 5 minutes (300 seconds)
        public int getHits(int timestamp) {
            // Evict hits older than 300 seconds from the front of the queue
            while (!queue.isEmpty() && timestamp - queue.peek() >= 300) {
                queue.poll();
            }
            return queue.size();
        }
    }

    public static void main(String[] args) {
        HitCounter counter = new HitCounter();
        System.out.println("--- Design Hit Counter Demonstration ---");
        
        System.out.println("Logging hits at seconds 1, 2, and 3...");
        counter.hit(1);
        counter.hit(2);
        counter.hit(3);
        
        System.out.println("Hits at second 4: " + counter.getHits(4) + " (Expected: 3)");
        System.out.println("Hits at second 300: " + counter.getHits(300) + " (Expected: 3)");
        System.out.println("Hits at second 301: " + counter.getHits(301) + " (Expected: 2) [Hit at second 1 expired]");
        
        System.out.println("\nLogging another hit at second 302...");
        counter.hit(302);
        System.out.println("Hits at second 302: " + counter.getHits(302) + " (Expected: 3) [Hits at 2, 3, 302 are active]");
    }
}

Conclusion

Designing a Hit Counter teaches us how to manage rolling time windows. By caching timestamp sequences inside a Queue, we can continuously prune expired logs in amortized constant time, preventing stale details from occupying memory.