Design a hit counter

01The design, in the six-step framework

1. Requirements and use cases

A phone-screen regular, last reported in January 2026. The first answer is a queue; the follow-ups are "what if there are millions of hits a second" and "what if hit and getHits run concurrently".

• A service records a hit at timestamp t, in seconds.
• A caller asks how many hits occurred in the 300 seconds ending at t.
• Timestamps arrive in non-decreasing order from a single caller (stated assumption).
• Several hits can share one timestamp.
• Follow-up: huge hit rates, and concurrent hit and getHits calls.

Out of scope: per-user counters (that is a rate limiter), durable storage, and sharing across machines. Non-functional constraints: memory must not grow with the hit rate, only with the window; hit in O(1); getHits in O(window) at worst, and O(1) if asked; and a 300-second window has a precise meaning that must be stated: hits at times in (t − 300, t].

2. Core entities and relationships

• HitCounter: the interface; hit and get_hits.
• QueueHitCounter: stores one timestamp per hit; the simple first version.
• BucketHitCounter: a fixed ring of 300 buckets, each with a second and a count.
• ConcurrentHitCounter: the ring split into striped locks so writers rarely collide.

Each implementation composes its own storage behind one interface, so the interview moves from one to the next without changing a caller. Starting with the queue is the right call under KISS: it is correct and takes two minutes, and then the follow-up gives you a reason for the ring. A bucket reuses its slot: if the stored second is not the one being written, the old count belongs to an earlier window and is overwritten.

3. Interfaces and key methods

from typing import Protocol


class HitCounter(Protocol):
    def hit(self, t: int) -> None:
        """Record one hit at second t. t never decreases for a given caller."""

    def get_hits(self, t: int) -> int:
        """Hits in (t - 300, t]. Read-only."""

Invariants for the ring: a bucket at index s % window holds a count for exactly the second it names; a bucket whose second is outside (t − window, t] counts for nothing; and memory is exactly window buckets, whatever the traffic.

memory = 300 buckets, whether the rate is 10 or 10,000,000 hits per second; the queue would hold 3,000,000,000 timestamps at the higher rate

4. Design patterns and the choices behind them

From a queue to a ring of buckets

The force is memory against precision. The queue stores every hit, so at ten million hits a second it holds three billion integers. The window only needs counts per second, so bucketing trades sub-second detail, which the API never exposes, for constant memory. Because the API resolves to one second, a one-second bucket loses nothing. If it resolved to milliseconds, the bucket count would be 300,000, or you would accept an approximate window.

Lazy reset instead of a sweeper

The force is expiring old seconds. A background thread that clears buckets adds a thread and a race. Storing the second in each bucket lets a write detect stale data and a read ignore it, which is lazy expiry in its plainest form.

Striping for concurrent writers

The force is contention. One lock around the ring makes every hit wait for the others. Splitting into S rings, each with its own lock and chosen by thread id, means writers rarely collide, and a read sums the stripes. Reads see a slightly stale sum across stripes, which is acceptable for a counter. This is the striped counter idea behind Java's LongAdder. A single atomic per bucket is the alternative, but the bucket reset is a compare of two fields, which needs a lock or a packed atomic word.

5. Core flow and code

Flow for the ring, with hits at seconds 1 and 301 and a read at 301:

1. hit(1): index 1 has a stale second, so it becomes second 1, count 1.
2. hit(301): 301 % 300 is index 1, whose second is 1, so the bucket is reset to second 301, count 1.
3. get_hits(301): each bucket counts only if its second is in (1, 301]. The sum is 1, because the hit at second 1 is exactly 300 seconds old.

import threading
from collections import deque
from dataclasses import dataclass
from typing import Deque, List


class QueueHitCounter:
    def __init__(self, window: int = 300) -> None:
        self.window = window
        self.hits: Deque[int] = deque()

    def hit(self, t: int) -> None:
        self.hits.append(t)

    def get_hits(self, t: int) -> int:
        while self.hits and self.hits[0] <= t - self.window:
            self.hits.popleft()
        return len(self.hits)


@dataclass
class Bucket:
    second: int = -1
    count: int = 0


class BucketHitCounter:
    def __init__(self, window: int = 300) -> None:
        self.window = window
        self.buckets: List[Bucket] = [Bucket() for _ in range(window)]

    def hit(self, t: int) -> None:
        bucket = self.buckets[t % self.window]
        if bucket.second != t:
            bucket.second, bucket.count = t, 0
        bucket.count += 1

    def get_hits(self, t: int) -> int:
        low = t - self.window
        return sum(b.count for b in self.buckets if low < b.second <= t)


class ConcurrentHitCounter:
    """Writers rarely share a stripe; a read sums all stripes and may lag by a few hits."""

    def __init__(self, window: int = 300, stripes: int = 8) -> None:
        self.stripes = [BucketHitCounter(window) for _ in range(stripes)]
        self.locks = [threading.Lock() for _ in range(stripes)]

    def hit(self, t: int) -> None:
        i = threading.get_ident() % len(self.stripes)
        with self.locks[i]:
            self.stripes[i].hit(t)

    def get_hits(self, t: int) -> int:
        total = 0
        for stripe, lock in zip(self.stripes, self.locks):
            with lock:
                total += stripe.get_hits(t)
        return total


if __name__ == "__main__":
    for c in (QueueHitCounter(), BucketHitCounter(), ConcurrentHitCounter()):
        c.hit(1); c.hit(1); c.hit(2); c.hit(300)
        assert c.get_hits(300) == 4
        assert c.get_hits(301) == 2          # both hits at second 1 left the window
        c.hit(301)
        assert c.get_hits(301) == 3

    shared = ConcurrentHitCounter()

    def writer() -> None:
        for _ in range(10000):
            shared.hit(5)

    threads = [threading.Thread(target=writer) for _ in range(4)]
    for th in threads:
        th.start()
    for th in threads:
        th.join()
    assert shared.get_hits(5) == 40000       # no lost updates

6. Extensions, concurrency and what interviewers probe

• The boundary. A hit exactly 300 seconds old is out. Fix the interval as (t − 300, t] and test it.
• Out-of-order timestamps. The ring tolerates them inside the window, because the bucket is chosen by the hit's own second. A very late hit could reset a newer bucket, so reject anything older than the window.
• Is a read lock needed? A read could skip locks and accept a torn sum for an approximate counter. If the interviewer wants exact, keep the locks.
• O(1) read. Keep a running total and subtract buckets as they age out; this needs in-order calls, and it adds a failure mode for little gain at a window of 300.
• Across machines. Each host keeps its own ring and a collector sums them; this is where the design stops being one class. See counters.
• Common mistake. Resetting a bucket on read, which turns a read into a write and creates a race, or indexing by t % 300 without storing the second, which adds counts from a window ago.

02Where this question was reported

• LeetCode Discuss · LeetCode 362 (Medium), Google-tagged, freq 33.8
• Taro · Taro Google page; follow-ups: very large hits/sec, concurrency needing locks/thread-safe structures
• Land the Lab · 'Design a hit counter' last asked Jan 2026