Practice/Uber/Leetcode 362. Design Hit Counter

Leetcode 362. Design Hit Counter

CodingMust

Problem

Build a system that tracks events (hits) as they occur and can quickly answer queries about how many events happened in the last 5 minutes (300 seconds). Your implementation should support two operations:

1. hit(timestamp): Record that an event occurred at the given timestamp
2. getHits(timestamp): Return the total number of events that occurred in the time range [timestamp - 299, timestamp] (inclusive)

The system must efficiently handle high-frequency operations while maintaining accurate counts within the sliding 300-second window.

Requirements

1. Implement a HitCounter class with a constructor and two methods: hit and getHits
2. The hit method should record an event at the specified timestamp
3. The getHits method should return the count of all events within the past 300 seconds from the query timestamp
4. All timestamps are in seconds and are strictly increasing (each call will have a timestamp greater than or equal to the previous call)
5. Multiple hits can occur at the same timestamp

Constraints

• 1 ≤ timestamp ≤ 2 × 10⁹
• All timestamps in input are in strictly non-decreasing order
• At most 300 calls will be made to hit
• At most 300 calls will be made to getHits
• Target time complexity: O(1) amortized for both operations
• Target space complexity: O(N) where N is the number of hits in the past 300 seconds

Examples

Example 1:

` Operations: ["HitCounter", "hit", "hit", "hit", "getHits", "hit", "getHits"] Arguments: [[], [1], [2], [3], [4], [300], [300]] Output: [null, null, null, null, 3, null, 4]

Explanation: HitCounter counter = new HitCounter(); counter.hit(1); // Record hit at timestamp 1 counter.hit(2); // Record hit at timestamp 2 counter.hit(3); // Record hit at timestamp 3 counter.getHits(4); // At time 4, all 3 hits are within [4-299, 4], return 3 counter.hit(300); // Record hit at timestamp 300 counter.getHits(300); // At time 300, all 4 hits are within [1, 300], return 4 `

Example 2:

` Operations: ["HitCounter", "hit", "hit", "hit", "getHits", "getHits"] Arguments: [[], [1], 2], [3], [4], [301]] Output: [null, null, null, null, 3, 2]

Explanation: HitCounter counter = new HitCounter(); counter.hit(1); // Record hit at timestamp 1 counter.hit(2); // Record hit at timestamp 2 counter.hit(3); // Record hit at timestamp 3 counter.getHits(4); // All 3 hits within window, return 3 counter.getHits(301); // Hit at timestamp 1 has expired (301-1=300), only hits at 2 and 3 remain, return 2 `