Logger Rate Limiter
Problem
Design a logger system that receives a stream of messages along with their timestamps and returns true if the message should be printed at the given timestamp, otherwise returns false, ensuring that a message is printed at most once every 10 seconds.
- All timestamps are non-negative integers.
- Timestamps are non-decreasing.
- Messages are arbitrary strings.
Example
timestamp = 1, message = "foo"; timestamp = 2, message = "bar"; timestamp = 3, message = "foo"; timestamp = 11, message = "foo"true, true, false, trueAt timestamp 1, "foo" is new, so print and record next allowed time as 11. At timestamp 2, "bar" is new, print and record next allowed time as 12. At timestamp 3, "foo" was printed at 1, so next allowed time is 11, current timestamp 3 < 11, so do not print. At timestamp 11, "foo" is allowed again (11 >= 11), so print and update next allowed time to 21.
Approach
Straightforward Solution
A naive approach might store all previous messages and their timestamps and scan through them to check if a message was printed in the last 10 seconds, resulting in inefficient lookups and updates.
Core Observation
Each message has its own 10-second cooldown after it is printed. To decide whether a message can be printed, track the earliest timestamp when that specific message is allowed to print again.
Path to Optimal
PreviewThe key insight is to use a hash map that maps each message to the earliest timestamp at which it can be printed again. This allows O(1) average-time checks and updates…
Full step-by-step walkthrough on Pro →
Optimal Approach
PreviewUse a hash map (dictionary) to store messages as keys and their next allowed print timestamp as values…
Full step-by-step walkthrough on Pro →
Want the full reasoning chain?
Unlock the complete walkthrough, line-by-line analysis, and recall drill.
Unlock ProTime
O(1)
Each message check and update involves a constant-time hash map lookup and insertion on average.
Space
O(m)
Space grows linearly with the number of unique messages stored in the hash map, where m is the number of distinct messages.
Pattern Spotlight
Hash Maps (Stateful Timestamp Tracking)
When needing to enforce time-based constraints per unique key, use a hash map to store the earliest allowed timestamp for each key, enabling constant-time validation and updates.
Solution
| 1 | class Logger: |
| 2 | |
| 3 | def __init__(self): |
| 4 | self.next_allowed_time = {} |
| 5 | |
| 6 | def shouldPrintMessage(self, timestamp: int, message: str) -> bool: |
| 7 | if message not in self.next_allowed_time: |
| 8 | self.next_allowed_time[message] = timestamp + 10 |
| 9 | return True |
| 10 | |
| 11 | if timestamp >= self.next_allowed_time[message]: |
| 12 | self.next_allowed_time[message] = timestamp + 10 |
| 13 | return True |
| 14 | |
| 15 | return False |
Step-by-Step Solution
Initialize Message to Next Allowed Timestamp Mapping
| 4 | self.next_allowed_time = {} |
Objective
To create a hash map that tracks the earliest timestamp at which each message can be printed again.
Key Insight
By storing the next allowed print time for each message, the logger can instantly determine if a message is eligible to be printed at the current timestamp. This avoids scanning past messages and enables constant-time checks.
Interview Quick-Check
Core Logic
The hash map stores messages as keys and their next allowed print timestamps as values, enabling O(1) access.
Common Pitfalls & Bugs
Failing to initialize the map or incorrectly updating timestamps can cause incorrect rate limiting.
Allow Printing for New Messages and Record Next Allowed Time
To permit printing of messages that have never been seen before and set their cooldown period.
Permit Printing if Cooldown Has Expired and Update Timestamp
To allow printing of messages whose cooldown period has elapsed and update their next allowed print time accordingly.
Reject Printing if Message is Still in Cooldown
To deny printing of messages that have been printed within the last 10 seconds.
3 more steps with full analysis available on Pro.
Line Analysis
This solution has 3 Critical lines interviewers watch for.
return FalseReturn false to indicate the message should not be printed due to active cooldown.
This line is the definitive enforcement of the rate limit; without it, messages could be printed too frequently, violating the problem's core requirement.
self.next_allowed_time[message] = timestamp + 10Set the next allowed print time for the new message to current timestamp plus 10 seconds.
This records the cooldown window for the message, preventing it from being printed again too soon.
if timestamp >= self.next_allowed_time[message]:Check if the current timestamp is at or beyond the message's next allowed print time.
This condition determines if the cooldown period has expired, allowing the message to be printed again.
Full line-by-line criticality + rationale for all 8 lines available on Pro.
Test Your Understanding
Why is a hash map the ideal data structure for tracking message print times in this problem?
See the answer with Pro.
Related Problems
Hash Maps pattern
Don't just read it. Drill it.
Reconstruct Logger Rate Limiter from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.
Unlock the Logger Rate Limiter drill