Skip to main content

26. Design Hit Counter

mediumAsked at Doordash

Build a counter that returns hits within a rolling 5-minute window — Doordash uses this real-time design pattern in their order-surge detection and Dasher-availability rate-limiting infrastructure.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Problem

Design a hit counter which counts the number of hits received in the past 5 minutes (i.e., the past 300 seconds). Your system should accept a timestamp parameter (in seconds) for the hit() function, and return the count of hits in the past 300 seconds for the getHits() function. Timestamps are monotonically increasing.

Constraints

  • 1 <= timestamp <= 2 * 10^9
  • All calls to hit() and getHits() use strictly increasing timestamps
  • At most 300 calls to hit() and getHits()

Examples

Example 1

Input
hit(1); hit(2); hit(3); getHits(4); hit(300); getHits(300); getHits(301)
Output
3, 4, 3

Explanation: At t=4: hits 1,2,3 all within 300s window. At t=301: hit at t=1 expires.

Approaches

1. Queue of timestamps

Append each hit timestamp to a queue. On getHits, evict all entries older than current - 300; return queue length.

Time
O(n) per getHits worst case
Space
O(n)
class HitCounter {
  constructor() { this.queue = []; }

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

  getHits(timestamp) {
    while (this.queue.length && this.queue[0] <= timestamp - 300) {
      this.queue.shift();
    }
    return this.queue.length;
  }
}

Tradeoff:

2. Circular bucket array (constant time)

Use 300 buckets (one per second slot). Each bucket stores [timestamp, count]. On hit, update the bucket for timestamp % 300 — overwrite if stale. On getHits, sum all 300 buckets that belong to the valid window.

Time
O(1) per hit; O(300) = O(1) per getHits
Space
O(300) = O(1)
class HitCounter {
  constructor() {
    this.times = new Array(300).fill(0);
    this.hits = new Array(300).fill(0);
  }

  hit(timestamp) {
    const idx = timestamp % 300;
    if (this.times[idx] !== timestamp) {
      this.times[idx] = timestamp;
      this.hits[idx] = 1;
    } else {
      this.hits[idx]++;
    }
  }

  getHits(timestamp) {
    let total = 0;
    for (let i = 0; i < 300; i++) {
      if (timestamp - this.times[i] < 300) {
        total += this.hits[i];
      }
    }
    return total;
  }
}

Tradeoff:

Doordash-specific tips

Doordash's real-time infrastructure team loves this problem because it directly models their order-surge rate tracker. Start with the queue approach to show correctness, then pivot to the circular array without being asked — proactively saying 'if timestamps are seconds and the window is fixed, I can trade 300 bytes of memory for O(1) per op' impresses. They'll ask how you'd extend to a 24-hour window or distributed hit counting — the bucket approach scales to Redis hash with a TTL per slot.

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Practice these live with InterviewChamp.AI

Drill Design Hit Counter and other Doordash interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →