Coding Interview PatternsDesign Hit Counter
MediumCustom Data Structures

Design Hit Counter

Explanation & Solution

Practice Problem

Description

Design a hit counter that counts the number of hits received in the past 300 seconds.

Implement a function that processes an array of operations and an array of arguments:

  • "HitCounter" — Initializes the hit counter.
  • "hit" — Records a hit at the given timestamp (in seconds). Multiple hits may have the same timestamp.
  • "getHits" — Returns the number of hits in the past 300 seconds from timestamp (inclusive of timestamp - 299 to timestamp).

The timestamp values passed to hit and getHits are non-decreasing.

Input:operations = ["HitCounter","hit","hit","hit","getHits","hit","getHits","getHits"], args = [[],[1],[2],[3],[4],[300],[300],[301]]
0
HitCounter
1
hit
2
hit
3
hit
4
getHits
5
hit
6
getHits
7
getHits
Output:[null,null,null,null,3,null,4,3]
0
null
1
null
2
null
3
null
4
3
5
null
6
4
7
3

Explanation: Hits at t=1,2,3. getHits(4) counts hits in [1..4] → 3. Hit at t=300. getHits(300) counts [1..300] → 4. getHits(301) counts [2..301] → 3 (t=1 is now outside the 300s window).

Constraints

  • 1 <= timestamp <= 2 * 10^9
  • All calls to hit and getHits are made in non-decreasing order of timestamp
  • At most 300 calls will be made to hit and getHits

Approach

Custom Data Structures pattern

1. Store Timestamps in Order

  • Maintain an array of all hit timestamps
  • Since timestamps are non-decreasing, the array is inherently sorted

2. Implement Hit

  • Simply append the timestamp to the array
  • Multiple hits at the same timestamp are stored as separate entries

3. Implement GetHits

  • Count how many stored timestamps t satisfy timestamp - t < 300
  • This means t > timestamp - 300, i.e., the hit is within the last 300 seconds
  • Since the array is sorted, scan from the back and break once a timestamp falls outside the window

4. Why Scan from the Back?

  • The most recent hits are at the end of the array
  • Since timestamps are non-decreasing, once you find a timestamp outside the window, all earlier ones are also outside — no need to continue

Key Insight

  • The 300-second window means a hit at timestamp t counts for any getHits(q) where q - t < 300
  • Boundary check: timestamp - hits[i] < 300 (strictly less than 300, not 300)
Time
O(n) per getHits, O(1) per hit
Space
O(n) for storing all hits

Solution Code

Previous
Design Browser History
Next
Design a Stack With Increment Operation