Problem 40.6 · Designing Data StructuresMedium

Design Hit Counter

PatternCombine Structures to Design Sliding Window: Variable Size

What it teaches: A sliding time window with a queue, or a fixed ring of 300 buckets for O(1) memory.

Practise it on judges as “Design Hit Counter”.

In plain words

A website counts visits and is often asked "how many visits in the last 5 minutes (300 seconds)?" Keep 300 little boxes, one per second, used in a circle like the seconds on a clock. Each box remembers which second it is counting right now; when a new second lands on an old box, empty it first. To answer, add up only the boxes whose second is recent enough.

Return the number of hits in the last 300 seconds. Example: hit(1), hit(2), hit(3), getHits(4), hit(300), getHits(300), getHits(301) → 3, 4, 3.

The problem

Design HitCounter with hit(timestamp) and getHits(timestamp) counting hits in the past 300 seconds (timestamp − 299 to timestamp). Timestamps never decrease.

Example 1

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

Constraints

Timestamps in seconds, non-decreasing

Pattern clues in the wording

→ Count events in the last N seconds
→ Rate limiting

These clues point to Combine Structures to Design: Pair a hash map (fast lookup) with a list, heap or tree (fast ordering) to meet every operation's time limit.

Stuck? Take one hint at a time

HitCounter · starter

class HitCounter {
    public HitCounter() {}
    public void hit(int timestamp) {}
    public int getHits(int timestamp) { return 0; }
}

Write your solution locally or in your editor for now. Pick Java, Python, C++, JavaScript or Go above: every solution on this page switches with it. The in-browser runner will run these tests right here.

Test cases

#	Input	Expected
1	ops = ["HitCounter","hit","hit","hit","getHits","hit","getHits","getHits"] args = [[],[1],[2],[3],[4],[300],[300],[301]]	[null,null,null,null,3,null,4,3]

+ 1 hidden test the code runner will check

From slow to fast

Approaches

1. Circular buckets · O(1) hit, O(300) getHits

Circular buckets

Time O(1) hit, O(300) getHits Space O(300)

times[i] and counts[i] for i = t % 300. On hit, reset the bucket if it holds an old second. getHits sums buckets whose time is within the window.

▶ Dry run: 300 circular buckets (slots 0–3 shown)hit(1), hit(2), hit(3), getHits(4), hit(300), getHits(300), getHits(301)

slot 0

slot 1

slot 2

slot 3

times(map)

slot 0: 0slot 1: 1slot 2: 2slot 3: 3

Step 1/5hit(1), hit(2), hit(3): slot = timestamp % 300. Each slot gets its timestamp and a count of 1. Cells show counts; the other 296 slots are all 0.

Approach 1

class HitCounter {
    private final int[] times = new int[300], counts = new int[300];

    public HitCounter() {}

    public void hit(int timestamp) {
        int i = timestamp % 300;
        if (times[i] != timestamp) { times[i] = timestamp; counts[i] = 0; }
        counts[i]++;
    }

    public int getHits(int timestamp) {
        int total = 0;
        for (int i = 0; i < 300; i++) if (timestamp - times[i] < 300) total += counts[i];
        return total;
    }
}

Verdict: Memory is constant even with millions of hits per second.

Before you submit

Edge cases and common mistakes

Test these inputs

Many hits in the same second
Long gaps between calls

Mistakes people make

Off-by-one at the window edge (a hit at t − 300 is outside).

Interview

Follow-up questions

How does this relate to rate limiters in production?

Connect the dots

Where this shows up in real systems

System Design · System 12.2 — Rate Limiter (HLD)Counting requests in the last N seconds is a sliding window over time.

Command Palette