Design Hit Counter — Sliding Window Queue with 5-Minute Retention

Problem Statement#

Design a hit counter which counts the number of hits received in the past 5 minutes (i.e., the past 300 seconds).

Your system should accept a timestamp parameter (in seconds granularity), and you may assume that calls are being made to the system in chronological order (i.e., timestamp is monotonically increasing). Several hits may arrive roughly at the same time.

Implement the HitCounter class:

• HitCounter() Initializes the object of the hit counter system.
• void hit(int timestamp) Records a hit that happened at timestamp (in seconds). Several hits may happen at the same timestamp.
• int getHits(int timestamp) Returns the number of hits in the past 5 minutes from timestamp, i.e., the past 300 seconds.

Constraints:

• 1 <= timestamp <= 2 * 10^9
• All calls are made in chronological order.
• At most 300 calls per timestamp.

HitCounter c;
c.hit(1); c.hit(2); c.hit(3);
c.getHits(4);   // 3
c.hit(300);
c.getHits(300); // 4
c.getHits(301); // 3

Why This Problem Matters#

LeetCode 362 Design Hit Counter is a foundational FAANG system design plus data structure question, especially popular at Amazon, Google, Meta, and Stripe. It is the smallest possible "rate-limited counter" problem — a building block of distributed rate limiters, real-time analytics dashboards, and DDoS protection systems.

The interview signal is high because there are three distinct correct solutions (queue of timestamps, circular buffer of 300 buckets, and TreeMap with binary search) and each illustrates a different trade-off. Recruiters expect you to enumerate them, pick one based on stated constraints, and reason about scale (what if hits-per-second can spike to billions?).

The Core Insight#

The naive approach stores every hit timestamp in a queue and dequeues stale entries on every call. That works but is O(n) for getHits in the worst case if many hits land at the same second.

Two production-grade approaches:

1. Circular buffer of 300 buckets. One bucket per second of the 300-second window. Each bucket stores (timestamp, count). On hit, hash timestamp mod 300 to a bucket; if the stored timestamp matches, increment, otherwise reset to (timestamp, 1). On getHits, iterate the 300 buckets and sum counts whose timestamp is greater than timestamp minus 300.

2. Queue of timestamps with deduplication. Keep a deque of timestamps, deduplicating equal timestamps with a count. Pop stale entries from the front on getHits or hit.

The bucket approach gives strictly bounded O(300) memory and O(300) getHits, regardless of hit rate. It is the canonical answer for the "scale to billions of hits per second" follow-up.

Visual Dry Run#

Using the queue-of-timestamps approach with hits at seconds 1, 2, 3, 300:

After three hits at 1, 2, 3 the deque holds [1, 2, 3].

getHits(4): window is (4 minus 300, 4] equals (-296, 4]. Front 1 is in range. No pops. Return length 3.

hit(300): deque becomes [1, 2, 3, 300].

getHits(300): window is (0, 300]. Front 1 is in range (1 greater than 0). Length 4.

getHits(301): window is (1, 301]. Front 1 is not greater than 1, pop. Deque becomes [2, 3, 300]. Length 3.

The bucket approach handles the same trace but with 300 fixed slots, so memory does not grow with the burst rate.

Solution (Optimal)#

I will show both. The bucket variant is the production answer; the deque variant is shorter for whiteboard.

from collections import deque
 
class HitCounter:
    def __init__(self):
        # 300 buckets: each holds [timestamp, count]
        self.buckets = [[0, 0] for _ in range(300)]
 
    def hit(self, timestamp: int) -> None:
        idx = timestamp % 300
        if self.buckets[idx][0] == timestamp:
            self.buckets[idx][1] += 1
        else:
            self.buckets[idx] = [timestamp, 1]
 
    def getHits(self, timestamp: int) -> int:
        total = 0
        for ts, count in self.buckets:
            if timestamp - ts < 300:
                total += count
        return total
 
 
class HitCounterQueue:
    def __init__(self):
        self.q = deque()  # stores raw timestamps
 
    def hit(self, timestamp: int) -> None:
        self.q.append(timestamp)
 
    def getHits(self, timestamp: int) -> int:
        while self.q and self.q[0] <= timestamp - 300:
            self.q.popleft()
        return len(self.q)

class HitCounter {
  constructor() {
    this.buckets = Array.from({ length: 300 }, () => [0, 0]);
  }
  hit(timestamp) {
    const idx = timestamp % 300;
    if (this.buckets[idx][0] === timestamp) this.buckets[idx][1]++;
    else this.buckets[idx] = [timestamp, 1];
  }
  getHits(timestamp) {
    let total = 0;
    for (const [ts, count] of this.buckets) {
      if (timestamp - ts < 300) total += count;
    }
    return total;
  }
}
 
class HitCounterQueue {
  constructor() {
    this.q = [];
    this.head = 0;
  }
  hit(timestamp) {
    this.q.push(timestamp);
  }
  getHits(timestamp) {
    while (this.head < this.q.length && this.q[this.head] <= timestamp - 300) {
      this.head++;
    }
    return this.q.length - this.head;
  }
}

Complexity (bucket). hit is O(1). getHits is O(300) which is effectively O(1). Memory is fixed at 300 entries.

Complexity (queue). hit is O(1) amortized. getHits is O(k) where k is the number of stale entries to pop, amortized O(1). Memory grows with concurrent hits — unbounded under bursts.

Common Mistakes#

• Using a regular Python list and pop(0) — O(n) per pop, kills throughput under high hit rates.
• Forgetting to bound the queue. Under a billion hits per second, the deque approach explodes.
• Hashing timestamp mod 300 but storing only the count, not the timestamp. You will conflate hits 600 seconds apart that fall into the same bucket.
• Using less-than-or-equal in the eviction comparison when the window is half-open. The exact boundary is timestamp minus 300 less than ts (i.e., ts greater than timestamp minus 300).
• Assuming timestamps are dense; they are monotonically increasing but can have gaps of any size.

Interview Tips#

• Always enumerate at least two approaches and discuss trade-offs. Recruiters expect this for design questions.
• For the bucket approach, explain why 300 is the magic number — one bucket per second of the window.
• Mention that the bucket approach generalizes: window of W seconds means W buckets.
• If asked about distributed scale, segue into Redis sorted sets, hyperloglog for approximate counts, or sliding window log algorithms.
• Mention the granularity trade-off — bucketing by second loses sub-second precision.

Follow-up Questions#

1. What if hits are extremely frequent (billions per second)? Use the 300-bucket approach; memory stays constant.
2. What if the window changes to W seconds? Use W buckets; trade memory for latency.
3. What if multiple threads call hit and getHits concurrently? Add per-bucket locks or use atomic operations on counters.
4. What if you must shard across machines? Each shard maintains a local hit counter; periodic merge or use a centralized aggregator.
5. What if the timestamp can be in the future or past (out of order)? Switch to a TreeMap or B-tree of timestamps with O(log n) insert.

Key Takeaways#

• A 300-bucket circular buffer gives constant memory and constant-time getHits regardless of hit rate.
• The deque-of-timestamps approach is shorter to write but unbounded under bursts.
• Both approaches exploit monotonic timestamps to evict stale data lazily.
• For distributed scale, escalate to Redis sorted sets, hyperloglog, or token bucket designs.
• The pattern generalizes to any "events in the last W seconds" queries — log analytics, rate limiting, fraud detection.
• Always discuss multiple approaches and trade-offs in design interviews.