362. Design Hit Counter

Q: Why is the circular buffer better than a queue?

Constant memory regardless of QPS. The queue grows with the hit rate; the buffer is always 300 slots. At Shopify's scale (hundreds of thousands of QPS), this difference is the difference between OOM and stable memory.

Q: What if multiple hits land on the same second?

Increment the count in that slot. The buffer stores (timestamp, count_at_that_timestamp), not just a count, so we can distinguish 'this slot was last touched at t=42' from 'this slot was last touched at t=342'.

mediumAsked at Shopify

Hit Counter is Shopify's rate-limiting interview classic. Storefronts log billions of hits per day, so the interviewer is grading whether you pick the right circular-buffer representation and discuss thread-safety and scale on the follow-up.

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

Source citations

Public interview reports confirming this problem appears in Shopify loops.

Glassdoor (2026-Q1)— Shopify Senior Production Engineer + Backend Developer onsites recurring data-structure design question.
Reddit r/cscareerquestions (2025-11)— Shopify SRE-track interview reports cite Hit Counter as the rate-limiting design round.

Problem

Design a hit counter which counts the number of hits received in the past 5 minutes (i.e., the past 300 seconds). The system accepts a timestamp parameter (in seconds granularity), and you may assume that calls are being made to the system in chronological order (timestamp is monotonically non-decreasing). Implement hit(timestamp) and getHits(timestamp).

Constraints

1 <= timestamp <= 2 * 10^9
All calls are in chronological order.
At most 300 calls per second to hit and getHits.

Examples

Example 1

Input

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

Output

[null,null,null,null,3,null,4,3]

Explanation: At t=301, the hit at t=1 falls outside the 300-second window.

Approaches

1. Naive queue of timestamps

Push each timestamp onto a queue. On getHits, pop all timestamps older than (now - 300), then return queue length.

Time: O(n) per getHits (amortized O(1) per hit)
Space: O(n)

class HitCounterQueue {
  constructor() { this.q = []; }
  hit(t) { this.q.push(t); }
  getHits(t) {
    while (this.q.length && this.q[0] <= t - 300) this.q.shift();
    return this.q.length;
  }
}

Tradeoff: Easy to write; memory is unbounded if hits arrive faster than they're pruned. Array.shift is O(n) — use a head pointer or a real deque for a real interview. Don't ship this past 'I see it'.

2. Circular buffer of (timestamp, count) pairs (optimal)

Keep two length-300 arrays indexed by (timestamp % 300). Each slot stores its last-written timestamp and the hit count for that exact second. On read, sum slots whose stored timestamp is within the window.

Time: O(1) hit, O(300) getHits
Space: O(300)

class HitCounter {
  constructor() {
    this.times = new Array(300).fill(0);
    this.counts = new Array(300).fill(0);
  }
  hit(timestamp) {
    const idx = timestamp % 300;
    if (this.times[idx] !== timestamp) {
      this.times[idx] = timestamp;
      this.counts[idx] = 1;
    } else {
      this.counts[idx]++;
    }
  }
  getHits(timestamp) {
    let total = 0;
    for (let i = 0; i < 300; i++) {
      if (timestamp - this.times[i] < 300) total += this.counts[i];
    }
    return total;
  }
}

Tradeoff: Constant memory (600 ints), constant-time hit, bounded-time read (300 iterations). The textbook answer Shopify expects. The clever bit: storing the timestamp alongside the count means we can reuse the same slot across multiple 300-second windows without explicit eviction.

Shopify-specific tips

Shopify's expected follow-up: 'what if the granularity is milliseconds, not seconds, and the window is an hour?' (1ms granularity x 3600s = 3.6M slots; use a coarser bucket — per-second buckets summed over the window). Senior candidates also get 'how do you distribute this across machines?' — answer: shard by (request_key) and aggregate via a stream processor; mention that exact counts are usually traded for approximate counts (HyperLogLog, Count-Min Sketch) at scale.

Common mistakes

Using `timestamp - this.times[i] <= 300` instead of `< 300` — off-by-one means hits at t=301 still count the hit at t=1.
Forgetting to reset the count when the slot's timestamp is overwritten (slot reuse across windows).
Array.shift in JS is O(n) — many candidates write the queue version without realizing the read is O(n^2) under load.
Not handling concurrent calls — interviewers ask about thread-safety as the immediate follow-up.

Follow-up questions

An interviewer at Shopify may pivot to one of these next:

Make it thread-safe.
Variable window size (e.g. last K seconds where K is a parameter).
Distributed version — multiple machines, eventually consistent counts.
Approximate counts at very high scale — Count-Min Sketch.
What if hits can arrive out of order (network jitter)?

Solve it now

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

Output

Press Run or Cmd+Enter to execute

FAQ

Why is the circular buffer better than a queue?

Constant memory regardless of QPS. The queue grows with the hit rate; the buffer is always 300 slots. At Shopify's scale (hundreds of thousands of QPS), this difference is the difference between OOM and stable memory.

What if multiple hits land on the same second?

Increment the count in that slot. The buffer stores (timestamp, count_at_that_timestamp), not just a count, so we can distinguish 'this slot was last touched at t=42' from 'this slot was last touched at t=342'.

Free learning resources

Curated free links for this problem.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →