Cruxly

Cruxly › Low-level design › LLD Exercises

Hit Counter

counting hits in the last N seconds without storing every hit forever

Open the interactive lesson

Prompt: design a hit counter that records a hit (hit(), called with the current timestamp) and reports how many hits occurred in the last 5 minutes (getHits(timestamp)), at a rate of thousands of hits per second.

45 minutes. Storing every hit's timestamp and counting how many fall in the window works, but it's the exercise's easy, wrong-for-scale answer — the real design bounds memory regardless of hit volume.

Applying the five moves: there is essentially one noun — a per-second Bucket (timestamp + count) — and recognizing that the individual hit does not need to be a stored object is the entire modelling insight; the naive model's Hit noun is the thing move 2 should delete. The invariant is "memory is O(window size in seconds), never O(number of hits)" — a bound stated as an invariant rather than a hope, which is what forces the ring-buffer shape rather than a growing list. There's no interface seam to add here, and the window size being a constructor parameter rather than an interface is worth saying explicitly — a WindowStrategy interface for a fixed 5-minute window is over-abstraction the interviewer will ask you to justify. Concurrency: thousands of hit() calls per second means the per-bucket increment is the contended path, and the honest answer names an atomic counter per bucket rather than a lock around the whole ring — plus the subtle part, which is that a bucket being recycled for a new second must reset before it accumulates, atomically with respect to readers.

Scope, and why storing every timestamp is the wrong shape

In scope: hit(timestamp), getHits(timestamp) returning the count in the trailing 5-minute window, bounded memory regardless of hit volume. Out of scope (say it): distributed counting across multiple servers (a much harder follow-up, name it separately), per-user or per-endpoint breakdowns, exact historical audit beyond the window.

Storing a list of every hit's timestamp and filtering to the last 5 minutes on getHits is correct and is the answer that fails the actual requirement — at thousands of hits per second, the stored list grows without bound (a hit from an hour ago is still sitting in memory even though it can never again be counted), and every getHits call has to at least touch every timestamp within the window, which is a lot of individual timestamps at this rate.

The number the design actually needs to bound is fixed regardless of hit volume: 300 one-second buckets for a 5-minute window. This reframes the problem entirely — instead of storing a timestamp per hit, store a count per second, in a fixed-size structure sized by the window length, not by how many hits occur. A million hits in one second is one bucket incrementing a million times, not a million stored entries.

The classes: a ring buffer of per-second counts

public class HitCounter {
    private static final int WINDOW_SECONDS = 300;   // 5 minutes
    private final long[] bucketTimestamp = new long[WINDOW_SECONDS];  // which second this slot currently represents
    private final int[] bucketCount = new int[WINDOW_SECONDS];        // hit count for that second

    public synchronized void hit(long timestamp) {
        int slot = (int) (timestamp % WINDOW_SECONDS);
        if (bucketTimestamp[slot] != timestamp) {
            // This slot belongs to an old second outside the current window —
            // reset it to the new second rather than accumulating onto stale data.
            bucketTimestamp[slot] = timestamp;
            bucketCount[slot] = 0;
        }
        bucketCount[slot]++;
    }

    public synchronized int getHits(long timestamp) {
        int total = 0;
        for (int i = 0; i < WINDOW_SECONDS; i++) {
            // Only count a slot if it actually represents a second inside the
            // trailing window — a slot can be reused by a future second and
            // still hold a stale timestamp if hit() hasn't touched it since.
            if (timestamp - bucketTimestamp[i] < WINDOW_SECONDS) {
                total += bucketCount[i];
            }
        }
        return total;
    }
}

The ring buffer is sized by the window length in seconds, not by expected hit volume — 300 slots regardless of whether the system sees ten hits a day or ten million hits a second. This is the entire design insight: memory is bounded by the requirement's time window, and hit volume only affects the magnitude of the integers stored, never the number of slots.

The lazy reset — checking bucketTimestamp[slot] != timestamp before incrementing — is what avoids needing a background sweeper to clear old buckets. A slot naturally gets reused every WINDOW_SECONDS seconds as time advances, and the check at the moment of reuse is what detects "this slot's old data is now stale" without any process needing to run on a schedule to clean it — the same lazy-expiry discipline as the rate limiter's token refill and the movie-booking seat hold elsewhere in this track.

Why per-second granularity, and the read/write cost trade

getHits doing a fixed 300-iteration scan on every call, rather than maintaining a running total updated incrementally, is a real design choice worth naming, not an oversight. A running total avoids the scan but requires correctly decrementing it as buckets age out of the window, which needs its own eviction logic — the fixed-scan version is simpler and, at 300 iterations, still fast in absolute terms; naming that this trade (simplicity versus a marginal constant-factor speedup) was made deliberately, not left undiscovered, is the point.

Concurrent hit() calls from many threads need real thread safety, not just a suggestion of it — the shown version uses a single lock across the whole structure, which is correct but serializes every hit through one critical section. At the stated thousands-per-second rate this is very likely fine (the critical section is a few array operations), but naming that a striped or per-bucket lock would be the next step if profiling showed contention, rather than assuming the coarse lock scales indefinitely, is the mature answer.

Follow-ups they will ask

"Support an arbitrary window length passed at query time, not just a fixed 5 minutes." This changes the data structure from a fixed ring buffer to something that supports arbitrary-range queries, like a per-second count stored in a structure supporting range-sum queries (a Fenwick tree or prefix-sum array over a longer retention period) — the ring buffer's fixed-size elegance specifically depends on there being one fixed window length, and generalizing it costs real complexity, worth naming as a different problem shape rather than a small parameter change.

"Scale this across multiple servers behind a load balancer, where hits for the same resource land on different machines." Each server's local HitCounter only sees its own share of hits — getting a global count requires either a shared counting store (Redis with per-second sorted-set or hash-based counters, incurring a network round-trip per hit) or periodic aggregation of each server's local counts into a central total, trading real-time accuracy for the simplicity of not making every single hit a network call.

"What if timestamps arrive out of order (network delay means an older hit's event arrives after a newer one)?" The lazy-reset logic above assumes monotonically non-decreasing timestamps arriving at hit() — an out-of-order hit for a timestamp behind the current bucket's timestamp would either get incorrectly reset into the wrong slot or silently miscounted, and this needs an explicit, stated policy (accept a small out-of-order tolerance window, or drop hits that arrive too late to place correctly) rather than an unstated assumption that time always moves forward cleanly.

How to say it in the interview

"Storing a timestamp per hit and filtering by the window on every read is correct but unbounded - at thousands of hits per second the storage and the per-query scan both grow without limit. The actual exercise is choosing a fixed-size structure - a ring buffer of per-second buckets - so both hit() and getHits() are bounded no matter how many hits actually occur."

Checklist

Practice this interactively
Share this lessonWhatsAppLinkedInX

Related lessons