Design Hit Counter
ID
362
Data Type
Queue
Difficulty
Medium
Tags
Sliding Window
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 attimestamp
(in seconds). Several hits may happen at the sametimestamp
.
int getHits(int timestamp)
Returns the number of hits in the past 5 minutes fromtimestamp
(i.e., the past300
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 tohit
andgetHits
.
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数量的总和即可。