Design Hit Counter

Build a class HitCounter that counts how many hits (for example page views) arrived during the last five minutes.

• HitCounter() creates a counter with no hits.
• hit(timestamp) records one hit at time timestamp, measured in seconds. Several hits may share the same timestamp.
• getHits(timestamp) returns the number of hits recorded in the 300 seconds ending at timestamp, that is, hits whose time t satisfies timestamp - 300 < t <= timestamp.

Calls arrive in time order: the timestamp passed to any call is never smaller than the one passed to the previous call.

Each test is a list of operations and a matching list of arguments; the expected output lists every return value, with null for the constructor and for hit.

Example 1

Example 2

Example 3

Constraints

• 1 <= timestamp <= 2 · 109
• Timestamps passed to successive calls never decrease.
• At most 3000 calls are made to hit and getHits combined.

Pattern Path · Design · problem 165 of 169

Start simple

Keep every hit forever and scan the whole list on each getHits call: O(total hits) per query and unbounded memory.

The key idea

Because timestamps never decrease, the hits form a sorted sequence and expiry always happens at the oldest end. That is exactly the shape of a queue.

hit(t) appends t to the back. getHits(t) first removes hits from the front while they are at or before t - 300. Those hits are outside the window now, and since later queries only have larger timestamps, they will never be inside a window again, so throwing them away is safe. Whatever remains is precisely the set of hits in the window, so the answer is the queue length.

Each hit is appended once and removed at most once, so the total work over all calls is linear and each call is amortised O(1). Memory holds only the hits from the last 300 seconds.

If a single second can contain millions of hits, switch to 300 buckets indexed by t % 300, each storing the second it represents and a count. Then memory is fixed at 300 entries and getHits sums the buckets whose second is still inside the window.

Complexity

• Time: O(1) amortised per call
• Space: O(hits in the last 300 seconds)

Python

from collections import deque

class HitCounter:
    WINDOW = 300

    def __init__(self):
        self.hits = deque()          # timestamps of hits, oldest first

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

    def getHits(self, timestamp):
        # Hits at or before timestamp - 300 can never count again: drop them.
        while self.hits and self.hits[0] <= timestamp - self.WINDOW:
            self.hits.popleft()
        return len(self.hits)

JavaScript

class HitCounter {
  constructor() {
    this.hits = [];   // timestamps of hits, oldest first
    this.head = 0;    // index of the oldest hit still in the window
  }

  hit(timestamp) {
    this.hits.push(timestamp);
  }

  getHits(timestamp) {
    // Hits at or before timestamp - 300 can never count again: skip them.
    while (this.head < this.hits.length && this.hits[this.head] <= timestamp - 300) {
      this.head++;
    }
    return this.hits.length - this.head;
  }
}

What the interviewer is checking

It tests whether you exploit the time-ordered input to discard stale data, and whether you can discuss memory trade-offs when traffic is heavy.

Mistakes to avoid

• Off-by-one on the window edge: a hit exactly 300 seconds old has expired (timestamp - 300 is excluded).
• Counting distinct timestamps instead of hits when several hits share a second.
• Only evicting old hits inside hit(), so getHits after a long quiet period still counts expired hits.
• Using list.pop(0) in Python, which makes each eviction O(n); use a deque or a moving head index.

Follow-ups to expect

• What if one second can have millions of hits? (300 buckets of (second, count).)
• What if calls come from many threads? (Lock or per-shard counters.)
• How would you support any window length? (Prefix counts plus binary search.)

In real software

Rate limiters, request-per-minute dashboards and abuse detection all keep sliding-window counts like this.

Practice next