Problem 74 · Object & System Design

Design Hit Counter

MediumClassic DSA & systems

01Problem

Design a counter with hit(timestamp) and get_hits(timestamp) returning hits in the past 300 seconds (inclusive window (t-300, t]). Timestamps are non-decreasing seconds and many hits can share a second.

02Key insight

Use a fixed circular buffer of 300 buckets, each holding (timestamp, count). A bucket whose stored timestamp is stale is reset on write and ignored on read, giving O(1) hit and O(W) read with constant memory regardless of traffic.

03Solution

solution.pypython15 lines

class HitCounter:
    def __init__(self, window: int = 300) -> None:
        self.window = window
        self.times = [0] * window
        self.counts = [0] * window

    def hit(self, timestamp: int) -> None:
        i = timestamp % self.window
        if self.times[i] != timestamp:
            self.times[i], self.counts[i] = timestamp, 0
        self.counts[i] += 1

    def get_hits(self, timestamp: int) -> int:
        return sum(c for t, c in zip(self.times, self.counts)
                   if timestamp - t < self.window)

Try it first.

TimeO(1) hit; O(W) get_hits

SpaceO(W)

tests.py · 4 passing

tests.pypython7 lines

hc = HitCounter()
hc.hit(1); hc.hit(2); hc.hit(3); hc.hit(3)
assert hc.get_hits(4) == 4
hc.hit(300)
assert hc.get_hits(300) == 5
assert hc.get_hits(301) == 4
assert hc.get_hits(1000) == 0

04Staff-level follow-up

Billions of hits across hosts? Each host keeps the bucket ring locally and ships per-second aggregates to a stream (Kafka) rolled up by key; buckets are mergeable by simple addition.