MediumArrayBinary SearchDesignQueueData StreamUpdated Sep 2026

362. Design Hit Counter

Asked at Apple, Databricks, Uber, Roblox

Difficulty

Medium

Time

O(1) amortized per call

Space

O(h) where h is the number of hi

Pattern

Array

Companies

4

Problem

Design a class called HitCounter that tracks how many hits happened in the last 5 minutes (the last 300 seconds).

Each hit has a timestamp in seconds. You may assume timestamps arrive in increasing order — never going backwards. Several hits can share the same timestamp.

Implement two methods:

  • hit(timestamp): record one hit at that time.
  • getHits(timestamp): return how many hits happened in the window [timestamp - 299, timestamp]. A hit exactly 300 seconds old is outside the window and must not be counted.

A hit at time t counts for getHits calls with timestamp up to t + 299.

Only the last 300 seconds count

hitswindow at t=300123300At t=300 the window is [1, 300], so all four hitscounthitswindow at t=301123300At t=301 the window is [2, 301], so the hit at 1 isnow too old
getHits(t) counts hits whose timestamp is in [t - 299, t]; anything older is ignored.

Constraints

  • ●1 <= timestamp <= 2 * 10^9
  • ●All calls are made in chronological order (timestamps are monotonically increasing).
  • ●At most 300 calls will be made to hit and getHits.

Examples

Example 1
Input["HitCounter", "hit", "hit", "hit", "getHits", "hit", "getHits", "getHits"] [[], [1], [2], [3], [4], [300], [300], [301]]
Output[null, null, null, null, 3, null, 4, 3]
WhyAfter hits at 1, 2 and 3, getHits(4) sees all three. The hit at 300 is added, so getHits(300) returns 4. At time 301 the window starts at 2, so the hit at 1 has expired and only 3 hits remain.
Example 2
Inputhit(1), hit(1), hit(1), getHits(2)
Output3
WhyThree hits share timestamp 1. All of them are inside the window ending at 2, so the answer is 3.
Example 3
Inputhit(1), getHits(301)
Output0
WhyThe window at 301 starts at 2. The hit at 1 is exactly 300 seconds old, which is too old, so it is dropped.

Asked At

4 companies
CompanyDifficulty
AppleMediumView all Apple questions →
DatabricksMediumView all Databricks questions →
UberMediumView all Uber questions →
RobloxMediumView all Roblox questions →

How to Think About It

1

Naive approach: store all timestamps in a list. On getHits, count how many timestamps fall within [timestamp - 299, timestamp]. This is O(n) per getHits call. Works but is slow if there are many hits.

2

Queue-based approach: store timestamps in a queue. On hit, enqueue the timestamp. On getHits, dequeue all timestamps older than 5 minutes, then return the queue size. Each timestamp is enqueued and dequeued at most once, so amortized O(1) per operation.

3

Circular buffer approach: since the window is fixed at 300 seconds, use an array of size 300. Each slot stores the count for that second modulo 300. On hit, increment the count at timestamp % 300. On getHits, sum all slots where the timestamp falls within the 5-minute window. This is O(300) = O(1) per getHits.

4

Queue approach is simpler and more intuitive. The circular buffer is more space-efficient but requires careful handling of stale data. For interviews, the queue approach is usually sufficient.

5

Time: O(1) amortized for both hit and getHits (queue approach). Space: O(hits) for queue, O(300) for circular buffer.

Optimal Approach

Queue approach:

  • hit(timestamp): append timestamp to the queue.
  • getHits(timestamp): while the front of the queue is <= timestamp - 300, pop it. Return the queue size.

Walkthrough with timestamps [1, 1, 1, 2, 2, 2, 301, 301, 302]:

  • hit(1): queue=[1]
  • hit(1): queue=[1,1]
  • hit(1): queue=[1,1,1]
  • hit(2): queue=[1,1,1,2]
  • hit(2): queue=[1,1,1,2,2]
  • hit(2): queue=[1,1,1,2,2,2]
  • hit(301): queue=[1,1,1,2,2,2,301]
  • hit(301): queue=[1,1,1,2,2,2,301,301]
  • hit(302): queue=[1,1,1,2,2,2,301,301,302]
  • getHits(303): pop while front <= 303-300=3. Pop 1,1,1,2,2,2 (all <= 3). queue=[301,301,302]. Return 3.

Time: O(1) amortized. Space: O(hits).

Queue that drops expired hits

queue123frontbackAfter hit(1), hit(2), hit(3): the queue holds allthree timestampsqueue123300frontbackhit(300) appends 300 at the back; nothing is removedyetqueue23300frontbackgetHits(301) pops 1 because 1 <= 301 - 300; the size 3is the answerpop while front <= t - 300answer = queue size
Push every hit at the back; before answering, pop from the front while the front is older than t - 299.
ComplexityTime O(1) amortized per callSpace O(h) where h is the number of hiEach timestamp is pushed once and popped at most once, so the total work across all calls is linear.

What Trips People Up in Real Interviews

1

Using a list and scanning all elements on every getHits call. This is O(n) per call. The queue approach is O(1) amortized because each element is removed at most once.

2

Confusing the 5-minute window. The window is [timestamp - 299, timestamp], not [timestamp - 300, timestamp). If a hit occurred at timestamp 1 and you query at timestamp 301, it should be excluded (301 - 300 = 1, and 1 <= 1 means it is at the boundary). Use <= timestamp - 300 to pop.

3

Not handling the case where timestamps are not strictly increasing. The problem guarantees strictly increasing timestamps, so you don't need to handle out-of-order arrivals. If the guarantee is removed, you need a sorted data structure.

4

Trying to use a deque with binary search for getHits. The queue with lazy deletion is simpler and equally efficient. Binary search adds unnecessary complexity.

5

Forgetting that getHits must not modify the queue permanently. The lazy deletion in the queue approach does remove old elements, which is correct because they will never be needed again (timestamps are strictly increasing).

Solution Code

O(1) amortized per call time
from collections import deque

class HitCounter:
    def __init__(self):
        self.q = deque()

    def hit(self, timestamp):
        self.q.append(timestamp)

    def getHits(self, timestamp):
        while self.q and self.q[0] <= timestamp - 300:
            self.q.popleft()
        return len(self.q)

Pro at DSA?

Test your skills with a real FAANG-style mock interview.

Start a Mock Interview →

Frequently Asked Questions

What is the Design Hit Counter problem?

Design a hit counter which counts the number of hits received in the past 5 minutes. Implement the `HitCounter` class: `HitCounter()` initializes the hit counter, `hit(timestamp)` records a hit at the given timestamp (guaranteed to be strictly increasing), and `getHits(timestamp)` returns the number of hits in the past 5 minutes (at timestamp).

How do you solve Design Hit Counter?

The optimal approach runs in O(1) amortized per call time and O(h) where h is the number of hi space. Scroll up to "Optimal Approach" for the step-by-step walkthrough, diagrams, and code in Python, C++ and Java.

What companies ask Design Hit Counter?

Design Hit Counter is asked at Apple, Databricks, Uber, Roblox. It is a medium difficulty problem.

What are common mistakes on Design Hit Counter?
  • Using a `list` and scanning all elements on every `getHits` call. This is `O(n)` per call. The `queue` approach is `O(1)` amortized because each element is removed at most once.
  • Confusing the 5-minute window. The window is [timestamp - 299, timestamp], not [timestamp - 300, timestamp). If a hit occurred at timestamp 1 and you query at timestamp 301, it should be excluded (301 - 300 = 1, and `1 <= 1` means it is at the boundary). Use `<= timestamp - 300` to pop.
  • Not handling the case where timestamps are not strictly increasing. The problem guarantees strictly increasing timestamps, so you don't need to handle out-of-order arrivals. If the guarantee is removed, you need a sorted data structure.
  • Trying to use a `deque` with binary search for `getHits`. The `queue` with lazy deletion is simpler and equally efficient. Binary search adds unnecessary complexity.
  • Forgetting that `getHits` must not modify the `queue` permanently. The lazy deletion in the `queue` approach does remove old elements, which is correct because they will never be needed again (timestamps are strictly increasing).