Introduction

A “hits in the last second, minute, or hour” structure is a sliding-window counting problem. You record timestamped events and then answer questions like “how many hits happened in the last 1 second, 60 seconds, or 3600 seconds?” The right design depends on whether your time windows are fixed and bounded or arbitrary and unbounded.

A Practical Fixed-Window Design

If the largest window is one hour, a ring buffer with one bucket per second is usually the cleanest solution. You keep 3600 slots, each storing:

• the timestamp that currently owns the slot
• the number of hits in that second

When a new hit arrives, you map its timestamp to timestamp % 3600. If the slot already belongs to the same second, increment the count. If it belongs to an older second, reset the slot and replace its timestamp.

This design gives:

• 'O(1) insert time'
• 'O(window) query time, where the window is at most 3600'
• fixed O(3600) memory

Because 3600 is a small constant, the query cost is often acceptable in practice.

Python Implementation

Here is a straightforward implementation:

1class HitCounter:
2    def __init__(self, max_window_seconds=3600):
3        self.max_window = max_window_seconds
4        self.timestamps = [0] * max_window_seconds
5        self.counts = [0] * max_window_seconds
6
7    def hit(self, timestamp: int) -> None:
8        index = timestamp % self.max_window
9        if self.timestamps[index] != timestamp:
10            self.timestamps[index] = timestamp
11            self.counts[index] = 1
12        else:
13            self.counts[index] += 1
14
15    def count_last(self, now: int, seconds: int) -> int:
16        if seconds > self.max_window:
17            raise ValueError("window exceeds configured maximum")
18
19        total = 0
20        for i in range(seconds):
21            ts = now - i
22            index = ts % self.max_window
23            if self.timestamps[index] == ts:
24                total += self.counts[index]
25        return total
26
27    def last_second(self, now: int) -> int:
28        return self.count_last(now, 1)
29
30    def last_minute(self, now: int) -> int:
31        return self.count_last(now, 60)
32
33    def last_hour(self, now: int) -> int:
34        return self.count_last(now, 3600)
35
36
37counter = HitCounter()
38for t in [100, 100, 101, 120, 3600, 3600, 3659]:
39    counter.hit(t)
40
41print(counter.last_second(3659))
42print(counter.last_minute(3659))
43print(counter.last_hour(3659))

This is a good interview and production baseline when timestamps are integer seconds.

Why the Ring Buffer Works

The modulo operation turns time into a circular array index. Old data eventually collides with new data, but that is safe because any data older than 3600 seconds is no longer relevant to the one-hour window.

The timestamp check prevents stale counts from being mistaken for current counts. That check is what makes overwriting safe.

Without storing the timestamp alongside the count, a slot reused an hour later would mix old and new events incorrectly.

When a Queue Is Better

If you need arbitrary windows rather than a known maximum, a deque of timestamps is often simpler. Insert every hit at the end, and on query, evict timestamps older than the relevant cutoff.

1from collections import deque
2
3class QueueHitCounter:
4    def __init__(self):
5        self.hits = deque()
6
7    def hit(self, timestamp: int) -> None:
8        self.hits.append(timestamp)
9
10    def count_last(self, now: int, seconds: int) -> int:
11        cutoff = now - seconds + 1
12        while self.hits and self.hits[0] < cutoff:
13            self.hits.popleft()
14        return len(self.hits)

That version is elegant, but it only supports one active sliding window cleanly at a time unless you maintain more structure. It also stores one entry per hit, which can grow large under heavy traffic.

Optimizing for Frequent Queries

If queries are very frequent and must be strictly O(1), you can maintain pre-aggregated rolling totals for 1 second, 60 seconds, and 3600 seconds. That adds implementation complexity because each new second forces totals to roll forward correctly.

In many real systems, the ring-buffer design is a better tradeoff:

• simple to reason about
• bounded memory
• fast enough for fixed windows up to one hour

Engineering time matters too, not just asymptotic notation.

Handling Clock Semantics

These designs assume timestamps are monotonically increasing integer seconds. If events can arrive late or out of order, you need to define the semantics clearly.

Options include:

• reject out-of-order hits
• accept them only if still inside the buffer horizon
• use event time instead of wall-clock time with more complex bookkeeping

For interview-style problems, monotonic timestamps are usually assumed. For production analytics pipelines, you must make that assumption explicit.

Common Pitfalls

The biggest pitfall is forgetting to store the timestamp per slot in a ring buffer. Without that, reused indices corrupt the counts.

Another issue is using one queue for multiple independently queried windows without thinking about eviction behavior.

People also often say their query is O(1) because the window size is fixed. That is fair in practice for 3600 slots, but it is still conceptually a bounded linear scan.

Finally, decide whether “last minute” includes the current second and document that boundary clearly.

Summary

• A ring buffer with one bucket per second is a strong solution for fixed windows up to one hour.
• Store both timestamp and count in each slot so stale data can be detected safely.
• Inserts are O(1) and queries are bounded by the largest configured window.
• A deque works well for simpler or more flexible sliding-window problems.
• Make timestamp ordering and window-boundary semantics explicit before coding the data structure.