Design Hit Counter — Count Requests in Last 300 Seconds

Problem

Design a hit counter that counts hits received in the past 5 minutes (300 seconds).

hit(timestamp) — record a hit at given timestamp (seconds granularity)
getHits(timestamp) — return number of hits in past 300 seconds

Timestamps are monotonically increasing. Hits at timestamp t count if t - 300 < hit_time <= t.

Solutions

Python — Deque (O(1) amortised)

from collections import deque

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

    def hit(self, timestamp: int) -> None:
        self.q.append(timestamp)

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

Python — Circular Buffer (handles many hits per second)

class HitCounter:
    def __init__(self):
        self.times = [0] * 300
        self.hits = [0] * 300

    def hit(self, timestamp: int) -> None:
        idx = timestamp % 300
        if self.times[idx] != timestamp:
            self.times[idx] = timestamp
            self.hits[idx] = 1
        else:
            self.hits[idx] += 1

    def getHits(self, timestamp: int) -> int:
        total = 0
        for i in range(300):
            if timestamp - self.times[i] < 300:
                total += self.hits[i]
        return total

JavaScript

class HitCounter {
    constructor() { this.times = new Array(300).fill(0); this.hits = new Array(300).fill(0); }
    hit(timestamp) {
        const i = timestamp % 300;
        if (this.times[i] !== timestamp) { this.times[i] = timestamp; this.hits[i] = 0; }
        this.hits[i]++;
    }
    getHits(timestamp) {
        let total = 0;
        for (let i = 0; i < 300; i++) if (timestamp - this.times[i] < 300) total += this.hits[i];
        return total;
    }
}

Java

class HitCounter {
    int[] times = new int[300], hits = new int[300];
    public void hit(int timestamp) {
        int i = timestamp % 300;
        if (times[i] != timestamp) { times[i] = timestamp; hits[i] = 0; }
        hits[i]++;
    }
    public int getHits(int timestamp) {
        int total = 0;
        for (int i = 0; i < 300; i++) if (timestamp - times[i] < 300) total += hits[i];
        return total;
    }
}

C++

class HitCounter {
    int times[300] = {}, hits[300] = {};
public:
    void hit(int timestamp) {
        int i = timestamp % 300;
        if (times[i] != timestamp) { times[i] = timestamp; hits[i] = 0; }
        hits[i]++;
    }
    int getHits(int timestamp) {
        int total = 0;
        for (int i = 0; i < 300; i++) if (timestamp - times[i] < 300) total += hits[i];
        return total;
    }
};

C

int times[300], hits_arr[300];
void hit(int timestamp) {
    int i = timestamp % 300;
    if (times[i] != timestamp) { times[i] = timestamp; hits_arr[i] = 0; }
    hits_arr[i]++;
}
int getHits(int timestamp) {
    int total = 0;
    for (int i = 0; i < 300; i++) if (timestamp - times[i] < 300) total += hits_arr[i];
    return total;
}

Complexity

Approach	hit	getHits	Space
Deque	O(1)	O(k)	O(k)
Circular	O(1)	O(300)	O(1)

The circular buffer is preferred in distributed systems — fixed memory, handles burst traffic.