362. Design Hit Counter

mediumAsked at Snap

Snap's view-count and snap-open-rate metrics run through a sliding-window counter — this problem is the foundational design exercise behind that system.

By Alex Chen, Founder, InterviewChamp.AI · Last verified 2026-05-26

Problem

Design a hit counter that counts the number of hits received in the past 5 minutes (300 seconds). Implement HitCounter with hit(timestamp) recording a hit at that second, and getHits(timestamp) returning hits in [timestamp-299, timestamp]. Timestamps are called in non-decreasing order.

Constraints

1 <= timestamp <= 2 * 10^9
All calls to hit and getHits use non-decreasing timestamps
At most 300 calls to hit and getHits

Examples

Example 1

Input

hit(1); hit(2); hit(3); getHits(4) → 3; hit(300); getHits(300) → 4; getHits(301) → 3

Output

[3,4,3]

Example 2

Input

hit(1); hit(1); getHits(1) → 2; getHits(301) → 0

Output

[2,0]

Approaches

1. Queue-based sliding window

Store all hit timestamps in a queue. On getHits, dequeue any timestamps older than 300 seconds from the front. Return queue length. Simple but uses unbounded memory when hit rate is high.

Time: O(n) per getHits
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

Fixed-size array of 300 buckets (one per second slot). Each bucket stores [timestamp, count]. On hit, mod timestamp by 300 to find slot; if the stored timestamp differs, reset count to 1, else increment. getHits sums all buckets whose stored timestamp is within the window. O(1) per operation, O(300) space regardless of hit rate.

Time: O(300) = O(1)
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:

Snap-specific tips

Snap's follow-up is almost always 'how do you scale this to multiple servers?' Mention consistent hashing to partition by user ID and a Redis sorted set (ZADD + ZREMRANGEBYSCORE) as the distributed answer.

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 Snap interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →