Logger Rate Limiter

Difficulty: Easy | Acceptance: N/A | Paid: No Topics: Hash Table, Design, Data Stream

Design a logger system that receives stream of messages along with their timestamps. Each message should be printed if and only if it has not been printed in the last 10 seconds.

Given a message and its timestamp (in seconds), return true if the message should be printed, otherwise false.

It is possible that several messages arrive roughly at the same time.

• Examples
• Constraints
• Brute Force
• Hash Map

Examples

Input
["Logger", "shouldPrintMessage", "shouldPrintMessage", "shouldPrintMessage", "shouldPrintMessage", "shouldPrintMessage", "shouldPrintMessage"]
[[], [1, "bad"], [2, "bad"], [3, "bad"], [8, "bad"], [10, "bad"], [11, "bad"]]
Output
[null, true, false, false, false, false, true]

Explanation
Logger logger = new Logger();
logger.shouldPrintMessage(1, "bad");  // return true, next allowed timestamp for "bad" is 1 + 10 = 11
logger.shouldPrintMessage(2, "bad");  // return false, 2 is less than 11
logger.shouldPrintMessage(3, "bad");  // return false, 3 is less than 11
logger.shouldPrintMessage(8, "bad");  // return false, 8 is less than 11
logger.shouldPrintMessage(10, "bad"); // return false, 10 is less than 11
logger.shouldPrintMessage(11, "bad"); // return true, 11 is equal to 11

Input
["Logger", "shouldPrintMessage", "shouldPrintMessage", "shouldPrintMessage"]
[[], [1, "foo"], [2, "bar"], [3, "foo"]]
Output
[null, true, true, false]

Constraints

0 <= timestamp <= 10^9
Every timestamp will be in strictly increasing order.
message will consist of lowercase English letters only.
The length of message will be in the range [1, 10].
At most 100 calls will be made to shouldPrintMessage.

Brute Force

Intuition Store every message that has been printed along with its timestamp in a list. When a new message arrives, iterate through the entire list to check if the same message was printed within the last 10 seconds.

Steps

• Initialize an empty list to store printed messages.
• When shouldPrintMessage is called, iterate through the list.
• If a message in the list matches the current message and the difference between the current timestamp and the stored timestamp is less than 10, return false.
• If the loop completes without finding a recent match, add the current message and timestamp to the list and return true.

class Logger:
    def __init__(self):
        self.history = []

    def shouldPrintMessage(self, timestamp: int, message: str) -> bool:
        for msg, ts in self.history:
            if msg == message and timestamp - ts < 10:
                return False
        self.history.append((message, timestamp))
        return True

Complexity

• Time: O(N) where N is the number of messages printed so far.
• Space: O(N) to store the history.
• Notes: This approach is inefficient for a large number of messages as it requires scanning the entire history for every new message.

Hash Map

Intuition Use a hash map (dictionary) to store the most recent timestamp for each unique message. This allows for O(1) lookups to check if a message was printed recently.

Steps

• Initialize an empty hash map.
• When shouldPrintMessage is called, check if the message exists in the map.
• If it exists, check if the difference between the current timestamp and the stored timestamp is greater than or equal to 10.
  • If yes, update the map with the new timestamp and return true.
  • If no, return false.
• If the message does not exist in the map, add it with the current timestamp and return true.

class Logger:
    def __init__(self):
        self.store = {}

    def shouldPrintMessage(self, timestamp: int, message: str) -> bool:
        if message in self.store:
            if timestamp - self.store[message] >= 10:
                self.store[message] = timestamp
                return True
            return False
        self.store[message] = timestamp
        return True

Complexity

• Time: O(1) average time complexity for hash map operations.
• Space: O(N) to store the last timestamp for each unique message.
• Notes: This is the optimal solution for this problem, providing constant time access and updates.