362. Design Hit Counter

Q: Why is the window exactly 300 seconds?

It's a fixed 5-minute window in the problem statement. Pinterest's real impression / rate-limit counters use multiple window sizes (1s, 1m, 1h) — they often ask the variable-window follow-up next.

Q: Does monotonic timestamps simplify the problem?

Yes. With out-of-order timestamps you'd need an indexed structure (sorted set or skip list); the bucket approach assumes time only moves forward.

mediumAsked at Pinterest

Pinterest's ads / metrics infrastructure runs on sliding-window counters. Design Hit Counter asks you to support hit(timestamp) and getHits(timestamp) over the last 300 seconds — the bucketed circular-array pattern is what production rate-limiters and impression counters use.

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

Source citations

Public interview reports confirming this problem appears in Pinterest loops.

Glassdoor (2026-Q1)— Pinterest L4/L5 onsite reports cite Design Hit Counter as the data-structures round for backend / ads-infra teams.
LeetCode Pinterest tag (2026-Q1)— High-frequency Pinterest-tagged problem on the company list.
Blind (2025-11)— Pinterest ads-infra candidate report walks through hit-counter as proxy for impression-tracking.

Problem

Design a hit counter that counts the number of hits received in the past 5 minutes (300 seconds). Implement hit(timestamp) which records a hit at the given UNIX timestamp (seconds), and getHits(timestamp) which returns the number of hits in the past 300 seconds (inclusive of timestamp). Calls are guaranteed to be made in monotonically non-decreasing timestamp order.

Constraints

1 <= timestamp <= 2 * 10^9
All calls are made with monotonically increasing timestamps.
At most 300 calls to hit and getHits.

Examples

Example 1

Input

HitCounter c; c.hit(1); c.hit(2); c.hit(3); c.getHits(4); c.hit(300); c.getHits(300); c.getHits(301);

Output

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

Explanation: At t=4, hits at 1,2,3 are within 300s — count is 3. At t=300 we've added a 4th. At t=301 the hit at t=1 has fallen out of the 300-second window.

Approaches

1. Queue of timestamps (brute force)

Push every hit timestamp into a queue. On getHits, shift expired entries (older than timestamp - 300) off the front and return the size.

Time: O(1) hit, O(n) getHits worst case where n = hits in window
Space: O(n)

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

Tradeoff: Correct and simple. Falls apart when hits arrive at high frequency because q.shift() is O(n) and memory grows unbounded for high-rate streams.

2. Bucketed circular array (optimal)

Two fixed-size arrays of length 300: one for timestamps and one for counts. Index by timestamp % 300. On hit/getHits, refresh the bucket if its timestamp is stale.

Time: O(1) hit, O(300) getHits (constant in window size)
Space: O(300) — constant

class HitCounter {
  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] += 1;
    }
  }
  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 regardless of hit rate; O(300) = O(window size) per query, which is independent of input size. This is the canonical sliding-window-counter pattern used in production rate-limiters and impression trackers.

Pinterest-specific tips

Pinterest interviewers care about two follow-up dimensions: (1) thread-safety — they will ask how you handle concurrent hit() calls; mention atomic counters or per-bucket locks. (2) scale — what if hits arrive a million per second? Talk about sharding by hash(userId) % N counter shards, then aggregating on read. Volunteer one of these before they ask.

Common mistakes

Using a heavyweight queue/linked-list instead of two fixed arrays — memory grows with hit rate.
Off-by-one on the window: a hit at timestamp t and a query at t + 300 should NOT include t (strictly less than 300 seconds ago).
Forgetting to reset the count when the bucket's timestamp is stale.
Using a single array of {time, count} objects with sort — defeats the constant-time-per-bucket structure.

Follow-up questions

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

Make it thread-safe.
Granularity smaller than 1 second (e.g. milliseconds).
Variable window size — last X seconds where X is a query parameter.
Distributed hit counter across a cluster.

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 window exactly 300 seconds?

It's a fixed 5-minute window in the problem statement. Pinterest's real impression / rate-limit counters use multiple window sizes (1s, 1m, 1h) — they often ask the variable-window follow-up next.

Does monotonic timestamps simplify the problem?

Yes. With out-of-order timestamps you'd need an indexed structure (sorted set or skip list); the bucket approach assumes time only moves forward.

Free learning resources

Curated free links for this problem.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →