362. Design Hit Counter

Q: Why is the bucketed version O(1) memory regardless of throughput?

Because the bucket array has fixed size 300. Multiple hits at the same timestamp just increment counts[ts % 300]. Hits at different timestamps within the window land in different buckets, never adding more than 300 slots.

Q: Can I generalize the bucket size?

Yes — for a window of W seconds with target granularity G, use W/G buckets and aggregate at second-resolution within each. The 300-bucket version uses G = 1s, the simplest config.

mediumAsked at Robinhood

Design a hit counter that counts the number of hits received in the past 5 minutes. Robinhood asks this because rolling-window counters are a daily-bread primitive for trading-system telemetry and abuse detection on order-placement APIs.

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

Source citations

Public interview reports confirming this problem appears in Robinhood loops.

Glassdoor (2026-Q1)— Robinhood SWE-II onsite reports list Design Hit Counter as a recurring design-coding hybrid.
Blind (2025-10)— Robinhood backend trip reports note rolling-window counter problems as a thematic favorite alongside rate limiters.

Problem

Design a hit counter which counts the number of hits received in the past 5 minutes (i.e., the past 300 seconds). Implement HitCounter with hit(int timestamp) and getHits(int timestamp). hit records a hit at the given timestamp; getHits returns the number of hits in the past 300 seconds (timestamp - 300 < t <= timestamp). The system runs in chronological order.

Constraints

1 <= timestamp <= 2 * 10^9
All the calls are being made in chronological order.
At most 300 calls will be made 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 are within 300s. At t=300: all four hits (1,2,3,300) are within 300s. At t=301: hit at t=1 expires; 3 remain.

Approaches

1. Queue of timestamps

Push every hit timestamp onto a queue. On getHits, evict head while head <= timestamp - 300, return queue.length.

Time: O(1) amortized hit, O(k) getHits worst case
Space: O(hits in window)

class HitCounter {
  constructor() {
    this.queue = [];
    this.head = 0;
  }
  hit(timestamp) {
    this.queue.push(timestamp);
  }
  getHits(timestamp) {
    while (this.head < this.queue.length && this.queue[this.head] <= timestamp - 300) {
      this.head++;
    }
    return this.queue.length - this.head;
  }
}

Tradeoff: Easy to write. Fine for small windows but memory is unbounded if hits per second is high — every hit is stored individually.

2. Bucketed counters (optimal for high-throughput)

Two parallel arrays of size 300: times[i] and counts[i]. Index by timestamp % 300. If times[i] !== current ts, reset counts[i] = 0.

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

class HitCounterBucketed {
  constructor() {
    this.times = new Array(300).fill(0);
    this.counts = new Array(300).fill(0);
  }
  hit(timestamp) {
    const i = timestamp % 300;
    if (this.times[i] !== timestamp) {
      this.times[i] = timestamp;
      this.counts[i] = 1;
    } else {
      this.counts[i]++;
    }
  }
  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 O(300) memory regardless of throughput — the right answer for a high-traffic counter. hit is O(1); getHits is O(300) but 300 is a fixed constant. Beats the queue version when hits-per-second is large.

Robinhood-specific tips

Robinhood will pivot to the high-throughput followup: 'What if 10 million hits arrive per second?' The bucketed version is the right answer because memory stays bounded at O(window-size) regardless of throughput. Be prepared to discuss thread safety briefly — at 10M hits/s the increment needs to be atomic or behind a lock-free counter.

Common mistakes

Using <= instead of < in the window boundary check — the spec is 'past 300 seconds', meaning timestamp - hit_ts < 300.
Forgetting to reset counts[i] when the slot belongs to an old timestamp — leaks hits from minutes ago.
Reading getHits as 'last 5 minutes from now' instead of 'last 300 seconds from the given timestamp' — the problem uses a passed-in clock, not wall time.

Follow-up questions

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

Sliding-window aggregation with arbitrary window size (not just 300s).
Track per-user hit counts (key by user_id, same bucketing).
Distributed hit counter — sketch sharding by hash(user_id) + per-shard window.

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 bucketed version O(1) memory regardless of throughput?

Because the bucket array has fixed size 300. Multiple hits at the same timestamp just increment counts[ts % 300]. Hits at different timestamps within the window land in different buckets, never adding more than 300 slots.

Can I generalize the bucket size?

Yes — for a window of W seconds with target granularity G, use W/G buckets and aggregate at second-resolution within each. The 300-bucket version uses G = 1s, the simplest config.

Free learning resources

Curated free links for this problem.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →