Design Hit Counter

mediumFREEStreaming & QueuesNetflix DSA

Design a hit counter that counts hits in the past 5 minutes (300 seconds).

Operations: hit,timestamp records a hit, getHits,timestamp returns hits in past 300 seconds.

Output results of each getHits call.

Example

Input

hit,1;hit,2;hit,3;getHits,4;hit,300;getHits,300;getHits,301

Output

3
4
3

Reasoning

Initially, hits are recorded at timestamps 1, 2, and 3.
At timestamp 4, getHits returns 3 because all previous hits (at 1, 2, and 3) are within the past 300 seconds.
At timestamp 300, getHits returns 4 because the hit at timestamp 300 is added to the previous hits that are still within the 300-second window (1, 2, 3, and 300).
At timestamp 301, getHits returns 3 because the hits at timestamps 1 and 2 are no longer within the past 300 seconds ( $301 - 300 = 1$ second has passed, and $300 - 1 = 299$ seconds have passed since the first hit), leaving hits at 3 and 300 within the window.

Constraints

1 <= timestamp <= 2 * 10^9
Timestamps are non-decreasing

Learn this in

FundamentalsDSA Study Plan

More from Netflix DSA

Search a 2D Matrixeasy Merge Intervalsmedium Sort Colorsmedium Kth Largest Element in an Arraymedium Missing Numbereasy

Concept primer

Background Knowledge

The problem of designing a hit counter that tracks hits within a specific time window (in this case, the past 5 minutes or 300 seconds) involves understanding queue data structures and time-based operations. A queue is a First-In-First-Out (FIFO) data structure, meaning the first element added to the queue will be the first one to be removed. This is particularly useful for tracking events over time, as newer events are added to the end of the queue, and older events are removed from the front.

Understanding how to efficiently manage the addition and removal of elements from a queue, especially when considering time as a factor, is crucial. This involves knowing how to timestamp each hit and how to determine which hits are within the specified time window. The concept of sliding window also comes into play, where the window of interest (the past 5 minutes) slides forward in time as new hits are recorded and old hits are discarded.

The ability to handle streaming data, where hits are coming in continuously, and to process these hits in real-time to provide an accurate count of hits within the past 5 minutes, is a key aspect of this problem. This requires an efficient algorithm that can handle the addition of new hits and the removal of old hits without significant overhead, ensuring that the getHits operation can return the correct count quickly.

Algorithm/Approach

The general approach to solving this type of problem involves using a queue to store the timestamps of hits. When a new hit is recorded, its timestamp is added to the queue. To ensure that only hits within the past 5 minutes are counted, the queue needs to be periodically cleaned up to remove timestamps that are older than 5 minutes. This cleanup process can be triggered either at regular intervals or whenever the getHits operation is called.

Step-by-Step Strategy

Initialize a queue to store the timestamps of hits.
When a hit,timestamp operation is called, add the timestamp to the queue.
When a getHits,timestamp operation is called, remove all timestamps from the queue that are older than 5 minutes from the given timestamp.
Count the remaining timestamps in the queue to determine the number of hits within the past 5 minutes.
Return the count of hits.

Common Pitfalls

Failing to remove old hits from the queue, leading to incorrect counts.
Not handling the case where the queue is empty or contains only outdated hits.
Implementing an inefficient cleanup mechanism that significantly slows down the getHits operation.

Time & Space Complexity

Time Complexity: The time complexity of adding a hit to the queue is $O(1)$ , and the time complexity of the getHits operation depends on the implementation of the queue cleanup. If done efficiently, it can be $O(n)$ , where $n$ is the number of hits within the time window.
Space Complexity: The space complexity is $O(n)$ , where $n$ is the maximum number of hits that can occur within the 5-minute window.

solution.py

Python 3.13

Test results