LeetCode 359 Logger Rate Limiter

LeetCode

Design a logger system that receives a stream of messages along with their timestamps. Each unique message should only be printed at most every 10 seconds (i.e. a message printed at timestamp t will prevent other identical messages from being printed until timestamp t + 10).

All messages will come in chronological order. Several messages may arrive at the same timestamp.

Implement the Logger class:

Logger() Initializes the logger object. bool shouldPrintMessage(int timestamp, string message) Returns true if the message should be printed in the given timestamp, otherwise returns false.

Example 1:

Input
[“Logger”, “shouldPrintMessage”, “shouldPrintMessage”, “shouldPrintMessage”, “shouldPrintMessage”, “shouldPrintMessage”, “shouldPrintMessage”]
[[], [1, “foo”], [2, “bar”], [3, “foo”], [8, “bar”], [10, “foo”], [11, “foo”]]
Output
[null, true, true, false, false, false, true]

Explanation
Logger logger = new Logger();
logger.shouldPrintMessage(1, “foo”);  // return true, next allowed timestamp for “foo” is 1 + 10 = 11
logger.shouldPrintMessage(2, “bar”);  // return true, next allowed timestamp for “bar” is 2 + 10 = 12
logger.shouldPrintMessage(3, “foo”);  // 3 < 11, return false
logger.shouldPrintMessage(8, “bar”);  // 8 < 12, return false
logger.shouldPrintMessage(10, “foo”); // 10 < 11, return false
logger.shouldPrintMessage(11, “foo”); // 11 >= 11, return true, next allowed timestamp for “foo” is 11 + 10 = 21

Constraints:

0 <= timestamp <= 10<sup>9</sup> Every timestamp will be passed in non-decreasing order (chronological order).
1 <= message.length <= 30 At most 10<sup>4</sup> calls will be made to shouldPrintMessage.

题目大意：

实现Logger打印的rate limiter

解题思路：

题不难，但有实际意义

解题步骤：

N/A

注意事项：

shouldPrintMessage只有返回True时候才记录时间点。否则不记录。这属于元素相等的test case

Python代码：

class Logger(TestCases):

    def __init__(self):
        self.throttle_interval = 10
        self.msg_to_timestamp = {}

    def shouldPrintMessage(self, timestamp: int, message: str) -> bool:
        if message in self.msg_to_timestamp and timestamp - self.msg_to_timestamp[message] < self.throttle_interval:
            return False
        self.msg_to_timestamp[message] = timestamp
        return True

算法分析：

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