Community Problem

Design Hit Counter

Difficulty: Medium

Build a counter that returns the number of hits in the past 5 minutes (300 seconds), with monotonically non-decreasing timestamps.

Design Hit Counter

Build a counter that returns the number of hits in the past 5 minutes (300 seconds), with monotonically non-decreasing timestamps.

MEDIUM

Free

sliding-window

deque

arrays

By @meibennett

January 4, 2026

Updated May 18, 2026

929 views

4.3 (13)

I had this on a Datadog backend onsite, in a round that doubled as the system-design warm-up. The interviewer cared about two things: (1) you handle the monotonic-timestamps assumption explicitly and (2) your getHits runs in time proportional to the WINDOW size, not the total history. The textbook answer is a deque (or circular buffer) of (timestamp, count) buckets, evicting anything older than 300 seconds.

Design Hit Counter

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 granularity), and you may assume that calls are being made to the system in chronological order (i.e., timestamp is monotonically non-decreasing). Several hits may arrive roughly at the same time.

Implement the HitCounter class:

HitCounter() initializes the object of the hit counter system.
void hit(int timestamp) records a hit that happened at timestamp (in seconds). Several hits may happen at the same timestamp.
int getHits(int timestamp) returns the number of hits in the past 5 minutes from timestamp (i.e., the past 300 seconds).

The past 5 minutes window is the half-open interval (timestamp - 300, timestamp].

Examples

Example 1:

HitCounter c = new HitCounter();
c.hit(1);            // hit at timestamp 1
c.hit(2);            // hit at timestamp 2
c.hit(3);            // hit at timestamp 3
c.getHits(4);        // 3 (hits 1, 2, 3 are within the window)
c.hit(300);          // hit at timestamp 300
c.getHits(300);      // 4 (hits 1, 2, 3, 300, all within (0, 300])
c.getHits(301);      // 3 (hit at 1 is now outside (1, 301])

Constraints

1 <= timestamp <= 2 * 10^9.
All calls are made in chronological order (i.e., timestamp is non-decreasing).
At most 300 calls will be made to hit and getHits.

Follow-up

What if the number of hits per second could be very large? Compress consecutive hits at the same timestamp into a single (timestamp, count) bucket; the deque length is at most one entry per distinct second within the window (300 entries).

Solution

JavaScript

Python

Hints

0/4

Hint 1

Hint 2

Hint 3

Hint 4

Solution Walkthrough

Approach: Deque of (Timestamp, Count) Buckets (O(1) amortized hit, O(window) getHits)

Store one bucket per distinct timestamp that's currently inside the 300-second window. Each bucket is [timestamp, count]. Maintain a running total so getHits is just "evict expired buckets, then return the total." Eviction walks from the front and removes buckets whose timestamp is <= now - 300 (i.e., outside the half-open (now - 300, now] window).

Key Insight

Text

Deque after hit(1), hit(2), hit(2), hit(300)
   buckets:  [[1, 1], [2, 2], [300, 1]]
   total:    4

getHits(301)
   cutoff = 301 - 300 = 1
   bucket[0] timestamp 1 <= 1, evict (total -= 1)
   bucket[1] timestamp 2 > 1, stop
   buckets:  [[2, 2], [300, 1]]
   return total = 3

Algorithm

For hit(timestamp):

If the last bucket's timestamp equals timestamp, increment its count.
Otherwise append [timestamp, 1].
Increment total.

For getHits(timestamp):

Compute cutoff = timestamp - 300.
While the front bucket's timestamp is <= cutoff, subtract its count from total and pop it.
Return total.

Why It Works

Monotonic timestamps guarantee buckets are in chronological order, so eviction only happens at the front. Coalescing same-second hits into one bucket bounds deque length to at most 300 entries (one per distinct second in the window), giving constant memory regardless of hit volume. The running total makes getHits constant-work after the eviction.

Complexity

Text

Metric                       Value
hit (amortized)              O(1)
getHits                      O(k) where k = expired buckets evicted on this call
Space                        O(min(window, distinct timestamps in window))

Across any sequence of M operations, total eviction work is O(M) (each bucket is created once and destroyed once), so amortized cost stays constant.

Pitfalls

Storing every hit individually. Works but blows up memory under high-rate input. Coalesce same-second hits.
Off-by-one on the window boundary. The window is (now - 300, now], so the cutoff comparison must be timestamp <= now - 300 (strict inequality means "already expired"), not <.
Re-summing on every getHits. Iterating the deque to compute the total each time is O(window). The running total field cuts that to O(evicted).
Using a JS Map keyed by timestamp. for...of on Map silently breaks under Sandpack's ES5 transpile. Stick with a plain array of [timestamp, count] pairs and a head pointer.
Forgetting to evict before answering. getHits must always evict first; otherwise stale buckets inflate the count.

Solution Code

All Problems