Design Hit Counter — Count Requests in Last 300 Seconds

Problem Statement#

Design a hit counter that counts the number of hits received in the past 5 minutes (300 seconds). Implement hit(timestamp) to record a hit and getHits(timestamp) to return the count of hits in the window (timestamp - 300, timestamp]. Timestamps are in seconds and arrive in monotonically non-decreasing order.

Constraints:

• 1 <= timestamp <= 2 * 10^9
• All timestamps passed to hit are non-decreasing
• At most 300 calls in total
• Multiple hits can arrive at the same timestamp

Input:  hit(1), hit(2), hit(3), getHits(4)
Output: 3

Input:  hit(1), hit(2), hit(3), getHits(300), getHits(301)
Output: 3, 2

Why This Problem Matters#

Hit counters power rate limiters, API quotas, and real-time analytics dashboards. AWS API Gateway, Cloudflare's rate limiter, and Nginx's limit_req module all use variants of the sliding window counter. The core design question is identical to this problem: how do you efficiently count events in the last N seconds with bounded memory?

This problem appears in Amazon and Stripe interviews because it tests your understanding of the fixed-size circular buffer—a pattern that achieves O(1) time and O(1) space regardless of how many hits arrive. Candidates who only know the deque approach miss this insight and produce an O(N) space solution that would fail at internet scale.

The circular buffer technique here is directly applicable to distributed rate limiting, where each server holds a 300-slot array and shares aggregated counts via Redis atomic operations.

The Core Insight#

The key observation: there are exactly 300 distinct seconds in the window. Map each second to a slot using timestamp % 300. When recording a hit, check if the stored timestamp for that slot matches the current timestamp. If not, this is a new epoch—reset the slot's count to 1. If it matches, increment the count.

For getHits, iterate over all 300 slots and sum those whose stored timestamp falls within the 300-second window (timestamp - stored_time < 300). This runs in exactly 300 iterations regardless of total hits.

The deque approach is simpler but stores one entry per hit—memory grows with traffic. The circular buffer uses exactly 600 integers of memory no matter the load.

Visual Dry Run#

Solution (Optimal)#

class HitCounter:
    def __init__(self):
        self.times = [0] * 300
        self.hits = [0] * 300
 
    def hit(self, timestamp: int) -> None:
        idx = timestamp % 300
        if self.times[idx] != timestamp:
            self.times[idx] = timestamp
            self.hits[idx] = 1
        else:
            self.hits[idx] += 1
 
    def getHits(self, timestamp: int) -> int:
        total = 0
        for i in range(300):
            if timestamp - self.times[i] < 300:
                total += self.hits[i]
        return total

class HitCounter {
    constructor() {
        this.times = new Array(300).fill(0);
        this.hits = new Array(300).fill(0);
    }
 
    hit(timestamp) {
        const i = timestamp % 300;
        if (this.times[i] !== timestamp) {
            this.times[i] = timestamp;
            this.hits[i] = 0;
        }
        this.hits[i]++;
    }
 
    getHits(timestamp) {
        let total = 0;
        for (let i = 0; i < 300; i++) {
            if (timestamp - this.times[i] < 300) total += this.hits[i];
        }
        return total;
    }
}

Time: O(1) for hit, O(300) = O(1) for getHits — constant regardless of traffic volume
Space: O(1) — two fixed-size arrays of length 300

Common Mistakes#

• Using <= vs < in the window check: the condition is timestamp - stored_time < 300, which means hits at timestamp - 299 are included but hits at timestamp - 300 are excluded
• Not resetting the count to 1 (instead of 0) when a new epoch starts at a slot, causing stale values from 300 seconds ago to persist
• The deque approach using while self.q and self.q[0] <= timestamp - 300 — the boundary is < timestamp - 299 which simplifies to <= timestamp - 300, so this is correct but easy to get wrong
• Not handling multiple hits at the same timestamp: the circular buffer handles this naturally via increment, but a naive deque stores duplicates
• Confusing the slot index timestamp % 300 with a time offset

Interview Tips#

• Always present both solutions: deque (simple, O(N) space) and circular buffer (optimal, O(1) space)
• Explain the slot reuse mechanism clearly: the same slot serves second 1, 301, 601, etc.
• Mention real-world applicability: this is the foundation of token bucket and sliding window rate limiters
• For distributed systems follow-up: each node has its own counter array; aggregate across nodes via Redis INCRBY on the same slot keys

Follow-up Questions#

• How would you support a configurable window size, not just 300 seconds? (Parameterise the array size to window_seconds)
• How would you handle out-of-order timestamps? (Use a sorted structure or ignore late arrivals)
• How would you scale to 10,000 requests/second across 100 servers? (Centralise counts in Redis with Lua scripts for atomicity)
• What if you needed millisecond granularity? (Use 300,000 slots or downsample to seconds)
• How would you support multiple named counters? (HashMap of {name: [times, hits]} arrays)

Key Takeaways#

• The circular buffer approach uses exactly 300 integer slots for any traffic volume—O(1) space
• Map timestamps to slots with timestamp % 300; detect epoch change by comparing stored timestamp to current
• getHits runs in exactly 300 iterations regardless of call frequency—O(1) practical runtime
• The deque approach is simpler but O(N) space where N is the number of hits in the window
• The boundary condition is timestamp - stored_time < 300 (strict less-than), not less-than-or-equal
• This design is used verbatim in sliding window rate limiters at API gateways
• Always handle multiple hits at the same timestamp: the circular buffer increments rather than overwrites