359. Logger Rate Limiter
Model: qwen2.5-coder:14b
Topics: Hash Table,Design
FAANG asked: 1
Acceptance rate: 72.5%
Problem Breakdown
The problem requires designing a logger system that processes messages with timestamps. Each unique message should only be printed at most once every 10 seconds. The input consists of method calls to shouldPrintMessage with a timestamp and a message string. The output is a boolean indicating whether the message should be printed at the given timestamp.
Inputs:
timestamp: An integer representing the time when the message arrives.message: A string representing the message content.
Outputs:
- A boolean value (
trueorfalse) indicating whether the message should be printed.
Implicit Constraints:
- Messages arrive in chronological order.
- The timestamp range is from 0 to (10^9).
- Message length ranges from 1 to 30 characters.
- There can be up to (10^4) calls to
shouldPrintMessage.
Intuition
A brute-force approach would involve storing all messages and their timestamps, checking each message against the current timestamp every time a new message arrives. This approach is inefficient in terms of both time and space complexity.
The key insight is to use a hash table (dictionary) to store the last printed timestamp for each message. This allows us to quickly check if a message should be printed by comparing the current timestamp with the stored timestamp plus 10 seconds.
Approach
- Data Structure Choice: Use a dictionary (
self.log) where keys are messages and values are their most recent timestamps. - Initialization: The
Loggerclass initializes an empty dictionary. - Method Implementation:
- If the message is not in the dictionary, add it with the current timestamp and return
true. - If the message is in the dictionary, check if the difference between the current timestamp and the stored timestamp is at least 10 seconds.
- If yes, update the timestamp and return
true. - If no, return
false.
- If yes, update the timestamp and return
- If the message is not in the dictionary, add it with the current timestamp and return
Complexity Analysis
- Time Complexity: (O(1)) for each call to
shouldPrintMessagebecause dictionary operations (insertion and lookup) are average (O(1)). - Space Complexity: (O(M)), where (M) is the number of unique messages stored in the dictionary.
Solution
class Logger:
def __init__(self):
# Initialize a dictionary to store message and its last printed timestamp
self.log = {}
def shouldPrintMessage(self, timestamp: int, message: str) -> bool:
# If the message is not in the log or the time difference is at least 10 seconds
if message not in self.log or timestamp - self.log[message] >= 10:
# Update the timestamp for this message
self.log[message] = timestamp
return True
else:
return False
Edge Cases Handled
- First Message: If a message is received for the first time, it will always be printed.
- Messages with Same Timestamp: Multiple messages can arrive at the same timestamp. The dictionary ensures that only one of them is printed if they are unique.
- Messages Repeated After 10 Seconds: A message that was not printed due to being within 10 seconds of its last print will be allowed after exactly 10 seconds have passed.
- Large Timestamps: The use of integer timestamps ensures that the solution works efficiently even with large values up to (10^9).