Design Hit Counter

Free with account Updated Nov 19, 2026 · 6 min read
On this page

    Problem statement

    Build a counter that records hits and reports how many hits happened in the last 5 minutes (300 seconds). hit(timestamp) records one hit at that second. getHits(timestamp) returns the number of hits in the window (timestamp − 300, timestamp]. Timestamps are in seconds and never decrease between calls; several hits can share the same second.

    This is a common warm-up for a longer round: once the basic version works, the interviewer usually pushes on memory when traffic is huge, on concurrency, and on making the window configurable. Original problem: LeetCode 362.

    Example

    At second 310 the window is (10, 310]: the two hits at second 10 are exactly 300 seconds old and drop out.
    At second 310 the window is (10, 310]: the two hits at second 10 are exactly 300 seconds old and drop out.
    hit(10); hit(10); hit(120); hit(299)
    getHits(300) -> 4        # window (0, 300]
    getHits(310) -> 2        # window (10, 310]: the hits at 10 have expired
    hit(310)
    getHits(310) -> 3
    getHits(610) -> 0

    Constraints (assumed)

    • 1 ≤ timestamp ≤ 2 × 10⁹; calls arrive in non-decreasing timestamp order.
    • Up to 10⁵ calls in the basic version; the follow-up allows millions of hits per second.

    What this question tests

    • Turning "the last 5 minutes" into an exact window boundary and testing the edge.
    • Choosing between a queue of events and fixed time buckets, and explaining the memory trade-off.
    • Talking through scale and concurrency once the simple version works.

    Questions to ask first

    1. Is the window inclusive? Does a hit exactly 300 seconds ago still count? (Here: no, the window is (t − 300, t].)
    2. Do timestamps arrive in order? (Here: yes, non-decreasing.)
    3. How many hits per second can there be? This decides queue vs buckets.
    4. Is the counter called from several threads? (Here: single-threaded first; concurrency is a follow-up.)
    5. Is the resolution one second? A finer resolution means more buckets.