KK's blog

每天积累多一些

0%

LeetCode 362 Design Hit Counter

Posted on Disqus:

LeetCode



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:

Input
[“HitCounter”, “hit”, “hit”, “hit”, “getHits”, “hit”, “getHits”, “getHits”]
[[], [1], [2], [3], [4], [300], [300], [301]]
Output
[null, null, null, null, 3, null, 4, 3]

Explanation
HitCounter hitCounter = new HitCounter();
hitCounter.hit(1);       // hit at timestamp 1.
hitCounter.hit(2);       // hit at timestamp 2.
hitCounter.hit(3);       // hit at timestamp 3.
hitCounter.getHits(4);   // get hits at timestamp 4, return 3.
hitCounter.hit(300);     // hit at timestamp 300.
hitCounter.getHits(300); // get hits at timestamp 300, return 4.
hitCounter.getHits(301); // get hits at timestamp 301, return 3.


Constraints: 1 <= timestamp <= 2 * 10<sup>9</sup>
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?

题目大意：

设计统计hits系统。题目要求：同一个时间可以有多个hits，hit是按时间顺序的。

解题思路：

用一个固定大小为300的数组来记录timestamp和对应的hits的总数

解题步骤：

N/A

注意事项：

  1. 题目要求：同一个时间可以有多个hits，hit是按时间顺序的。所以固定数组只要比较现在的timestamp是否和last_timestamp一样，不是的话reset hit。用循环数组记录
  2. getHist是统计300以内（不包括300）的hit数。

Python代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class HitCounter(TestCases):

    def __init__(self):
        self.hits = [(0, 0)] * 300

    def hit(self, timestamp: int) -> None:
        last_timestamp, count = self.hits[timestamp % 300]
        if last_timestamp and timestamp != last_timestamp:
            self.hits[timestamp % 300] = (timestamp, 0)
            count = 0
        count += 1
        self.hits[timestamp % 300] = (timestamp, count)

    def getHits(self, timestamp: int) -> int:
        res = 0
        for t, count in self.hits:
            if t and timestamp - t < 300:
                res += count
        return res

算法分析：

hit时间复杂度为O(1)，getHits时间复杂度为O(1)，空间复杂度O(1)

Free mock interview