Design Hit Counter
|Last edited: 2024-5-9
ID
362
Data Type
Queue
Difficulty
Medium
Tags
Sliding Window
URL
https://leetcode.com/problems/design-hit-counter
Completed Date
Preference
💸😭 Poverty Tears
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 increasing). 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).
Example 1:
Constraints:
  • 1 <= timestamp <= 2 * 109
  • All the calls are being made to the system in chronological order (i.e., timestamp is monotonically increasing).
  • At most 300 calls will be made to hit and getHits.
Follow up: What if the number of hits per second could be huge? Does your design scale?
 

题解

这是一个经典的滑动窗口问题。我们需要设计一个hit计数器，用于计算过去5分钟内（300秒）接收到的hit数量。我们可以使用一个队列来保存所有的hit，每当有新的hit到达时，我们将其添加到队列的末尾。同时，我们从队列的头部删除所有时间戳小于当前时间戳-300的hit。这样，队列中始终保持的是过去5分钟内的hit。当我们需要获取过去5分钟内的hit数量时，我们只需要返回队列的长度即可。
这种设计在每秒的hit数量不是非常大的情况下是可行的。但是，如果每秒的hit数量可能非常大，那么我们需要考虑如何扩展我们的设计。一种可能的方法是使用一个哈希表来保存每个时间戳和对应的hit数量。这样，我们只需要在每个新的时间戳到达时更新哈希表，并删除所有时间戳小于当前时间戳-300的记录。当我们需要获取过去5分钟内的hit数量时，我们只需要计算哈希表中所有hit数量的总和即可。