Design Hit Counter

This is a classic systems-flavored question. Count the hits in the last five minutes. It sounds easy. The trick is throwing away hits that are too old without slowing down. How you forget old data is the whole puzzle here.

🎯 The Problem

You build a counter that records hits and reports how many landed recently.

What a hit is:

• A hit is one event, like one page view.
• Each hit comes with a timestamp in seconds.

The operations:

• hit(time) records one hit at that time.
• getHits(time) returns how many hits happened in the past 5 minutes, counting back from that time.

The rules:

• Five minutes is 300 seconds.
• A hit at timestamp h still counts at time t when t minus h is less than 300.
• A hit drops out once t minus 300 reaches its timestamp.
• Timestamps only ever go up, never back.

hit(1)         -> record a hit at second 1
hit(2)         -> record a hit at second 2
hit(3)         -> record a hit at second 3
getHits(4)     -> 3   (seconds 1, 2, 3 are all within the last 300)
hit(300)       -> record a hit at second 300
getHits(300)   -> 4   (seconds 1, 2, 3, 300 all count)
getHits(301)   -> 3   (second 1 dropped: 301-300=1 reaches timestamp 1)
getHits(302)   -> 2   (second 2 dropped too: 302-300=2 reaches timestamp 2)

So as time moves forward the oldest hits fall out one by one. At second 301 the hit at second 1 is gone. At second 302 the hit at second 2 is gone too. We let the queue do this dropping for us.

Here is the sliding window. Old hits drop off the left as time moves right.

🐢 Approach 1: Keep Every Hit and Scan (Brute Force)

The idea in one line: store every hit timestamp in a list, then count the recent ones on each read.

The idea:

• Store every hit timestamp in a list.
• hit just appends the timestamp.
• getHits walks the whole list and counts the ones newer than time - 300.

Why it is weak:

• The list grows forever. Hits from hours ago never leave.
• Every read scans the entire list.
• With millions of old hits, each read scans all of them.

Here is the keep-every-hit code:

class HitCounter:
    def __init__(self):
        self.hits = []

    def hit(self, timestamp):
        self.hits.append(timestamp)

    def getHits(self, timestamp):
        return sum(timestamp - 300 < time <= timestamp for time in self.hits)

⚡ Approach 2: Queue of Timestamps (Better)

The idea in one line: hold hits oldest first, then drop the expired ones off the front before each read.

The idea:

• A queue is a line. You add at the back and remove from the front.
• Old hits sit at the front, because timestamps only go up.
• New hits join the back.

How it works:

• On each operation, clean the front first.
• While the front timestamp is 300 or more seconds old, remove it.
• hit adds to the back. getHits returns the queue size after cleaning.

Why it is fast:

• Each hit is added once and removed once.
• We never re-scan old hits. They leave the front and never return.
• Cleaning is O(1) on average across many calls.

Here is the timestamp-queue code:

from collections import deque


class HitCounter:
    def __init__(self):
        self.hits = deque()

    def hit(self, timestamp):
        self.hits.append(timestamp)

    def getHits(self, timestamp):
        while self.hits and self.hits[0] <= timestamp - 300:
            self.hits.popleft()
        return len(self.hits)

🪟 Approach 3: Circular Buffer of 300 Slots (Best for Bursts)

The idea in one line: use a fixed array of 300 slots, one per second, so memory never grows even under huge bursts.

The idea:

• A circular buffer is a fixed array that wraps around.
• Keep 300 slots, one per second of the window.
• Each slot stores a timestamp and a count.

How it works:

• To record a hit, look at slot time % 300.
• If the slot’s timestamp matches this second, add one to its count.
• If not, the slot is stale, so reset it to this time with count one.
• For a read, sum the counts of all slots whose time is within the last 300 seconds.

Why it is fast:

• Fixed 300 slots no matter how many hits arrive.
• A burst of hits in one second is just one slot getting bigger.
• Memory stays flat. Good when hits arrive in large bursts.

Here is the queue cleaning out expired hits at time 302.

Steps to Solve

1. Keep a queue of hit timestamps, oldest at the front.
2. For hit, add the timestamp to the back of the queue.
3. For getHits, first remove from the front while the front timestamp is 300 or more seconds older than now.
4. After cleaning, return the number of timestamps left in the queue.
5. For the circular buffer version, keep 300 slots, each with a timestamp and a count.
6. On hit, update slot time % 300. If its stored time differs, reset that slot. Otherwise add one.
7. On getHits, sum the counts of all slots whose time is within the last 300 seconds.

#include <stdio.h>

#define WINDOW 300

int times[WINDOW];   // timestamp stored in each slot
int counts[WINDOW];  // how many hits in that slot

void hit(int t) {
    int i = t % WINDOW;
    if (times[i] != t) {     // slot is stale, reset it
        times[i] = t;
        counts[i] = 1;
    } else {
        counts[i]++;         // same second, add one
    }
}

int getHits(int t) {
    int total = 0;
    for (int i = 0; i < WINDOW; i++)
        if (t - times[i] < WINDOW)   // slot is inside the window
            total += counts[i];
    return total;
}

int main(void) {
    hit(1); hit(2); hit(3);
    printf("getHits(4) -> %d\n", getHits(4));
    hit(300);
    printf("getHits(300) -> %d\n", getHits(300));
    printf("getHits(301) -> %d\n", getHits(301));
    printf("getHits(302) -> %d\n", getHits(302));
    return 0;
}

getHits(4) -> 3
getHits(300) -> 4
getHits(301) -> 3
getHits(302) -> 2

#include <iostream>
#include <queue>
using namespace std;

class HitCounter {
    queue<int> hits;  // timestamps, oldest at the front
public:
    void hit(int t) {
        hits.push(t);          // add to the back
    }
    int getHits(int t) {
        while (!hits.empty() && hits.front() <= t - 300)
            hits.pop();        // drop expired hits from the front
        return hits.size();
    }
};

int main() {
    HitCounter c;
    c.hit(1); c.hit(2); c.hit(3);
    cout << "getHits(4) -> " << c.getHits(4) << endl;
    c.hit(300);
    cout << "getHits(300) -> " << c.getHits(300) << endl;
    cout << "getHits(301) -> " << c.getHits(301) << endl;
    cout << "getHits(302) -> " << c.getHits(302) << endl;
    return 0;
}

getHits(4) -> 3
getHits(300) -> 4
getHits(301) -> 3
getHits(302) -> 2

import java.util.LinkedList;
import java.util.Queue;

public class HitCounter {
    private Queue<Integer> hits = new LinkedList<>(); // oldest at the front

    public void hit(int t) {
        hits.add(t);            // add to the back
    }

    public int getHits(int t) {
        while (!hits.isEmpty() && hits.peek() <= t - 300)
            hits.poll();        // drop expired hits from the front
        return hits.size();
    }

    public static void main(String[] args) {
        HitCounter c = new HitCounter();
        c.hit(1); c.hit(2); c.hit(3);
        System.out.println("getHits(4) -> " + c.getHits(4));
        c.hit(300);
        System.out.println("getHits(300) -> " + c.getHits(300));
        System.out.println("getHits(301) -> " + c.getHits(301));
        System.out.println("getHits(302) -> " + c.getHits(302));
    }
}

getHits(4) -> 3
getHits(300) -> 4
getHits(301) -> 3
getHits(302) -> 2

from collections import deque


class HitCounter:
    def __init__(self):
        self.hits = deque()    # timestamps, oldest at the front

    def hit(self, t):
        self.hits.append(t)    # add to the back

    def get_hits(self, t):
        while self.hits and self.hits[0] <= t - 300:
            self.hits.popleft()  # drop expired hits from the front
        return len(self.hits)


c = HitCounter()
c.hit(1)
c.hit(2)
c.hit(3)
print("getHits(4) ->", c.get_hits(4))
c.hit(300)
print("getHits(300) ->", c.get_hits(300))
print("getHits(301) ->", c.get_hits(301))
print("getHits(302) ->", c.get_hits(302))

getHits(4) -> 3
getHits(300) -> 4
getHits(301) -> 3
getHits(302) -> 2

class HitCounter {
  constructor() {
    this.hits = []; // timestamps, oldest at the front
  }

  hit(t) {
    this.hits.push(t); // add to the back
  }

  getHits(t) {
    while (this.hits.length && this.hits[0] <= t - 300) {
      this.hits.shift(); // drop expired hits from the front
    }
    return this.hits.length;
  }
}

const c = new HitCounter();
c.hit(1);
c.hit(2);
c.hit(3);
console.log("getHits(4) ->", c.getHits(4));
c.hit(300);
console.log("getHits(300) ->", c.getHits(300));
console.log("getHits(301) ->", c.getHits(301));
console.log("getHits(302) ->", c.getHits(302));

getHits(4) -> 3
getHits(300) -> 4
getHits(301) -> 3
getHits(302) -> 2

Let us walk through the Python get_hits method line by line, because the cleaning step is the heart of this design.

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

The line while self.hits and self.hits[0] <= t - 300 is the cleaning loop. self.hits[0] is the oldest timestamp at the front. The check <= t - 300 asks if that hit is 300 or more seconds old. If yes, it is outside the five minute window.

So why the front? Because timestamps only go up, the oldest hit is always at the front. Once a front hit is too old, every later hit is newer, but the front itself must go.

The line self.hits.popleft() removes that expired hit from the front. popleft on a deque is O(1), so dropping the front is cheap. The loop keeps going until the front is fresh again.

The line return len(self.hits) returns how many hits are left. After cleaning, every timestamp in the queue is inside the window. So the count is just the size.

Trace it at second 302. By then earlier calls already dropped the hit at second 1, so the queue holds 2, 3, 300. We need front <= 302 - 300, which is <= 2. The front is 2, so it drops. The next front is 3, and 3 is not <= 2, so we stop. The queue is now 3 and 300, and the answer is 2. That matches the printed output.

⏱️ Time and Space Complexity

The naive list grows forever and scans everything, so it is slow and heavy. The queue version adds each hit once and removes it once, so the total work stays small. Each getHits only drops the hits that just expired. The circular buffer uses a fixed 300 slots no matter how many hits arrive, so its space never grows.

🧩 Key Takeaways

• ✅ Count over a time window means forget the old data, do not keep scanning it.
• ✅ A queue holds hits oldest first, so you clean the front and the rest is the answer.
• ✅ Cleaning the front is O(1) amortized, because each hit leaves the queue only once.
• ✅ A circular buffer of 300 slots uses fixed memory even under huge bursts.
• ✅ Pick the queue for clarity, and the circular buffer when memory must stay flat.

🚀 What’s Next?

• Snapshot Array
• All O’one Data Structure