Watch 10 video solutions for Logger Rate Limiter, a easy level problem involving Hash Table, Design, Data Stream. This walkthrough by Cracking FAANG has 8,453 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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 <= 109timestamp will be passed in non-decreasing order (chronological order).1 <= message.length <= 30104 calls will be made to shouldPrintMessage.Problem Overview: You need to design a logger system that decides whether a message should be printed at a given timestamp. Each message can only be printed once every 10 seconds. If the same message appears again within that window, the logger must suppress it.
Approach 1: Brute Force Log Scan (O(n) time, O(n) space)
Store every printed message with its timestamp in a list or queue. When a new request arrives, iterate through the stored logs to find the most recent occurrence of that message. If the difference between the current timestamp and the stored timestamp is at least 10 seconds, allow printing; otherwise reject it. This approach works but becomes inefficient as the log grows because every query may require scanning multiple entries. The time complexity per request can degrade to O(n), while space complexity is also O(n) for storing past messages.
Approach 2: Hash Table with Last Printed Timestamp (O(1) time, O(n) space)
Use a hash table that maps each message string to the last timestamp when it was printed. For every incoming message, perform a constant-time lookup in the map. If the message is not present, or if currentTimestamp - lastTimestamp >= 10, update the stored timestamp and return true. Otherwise return false. Hash lookups and updates run in O(1) average time, making this approach extremely efficient for continuous streams of log events.
This technique fits naturally with design problems where the system must respond quickly to frequent queries. Since messages arrive in chronological order (a typical assumption in data stream problems), the stored timestamps remain valid without extra cleanup logic. The space usage grows with the number of unique messages and is O(n).
Recommended for interviews: The hash table approach is the expected solution. It demonstrates the ability to convert repeated lookups into constant-time operations using a map. Mentioning the brute force scan shows you understand the baseline, but implementing the hash map version shows strong problem-solving and system design instincts.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Log Scan | O(n) per request | O(n) | Conceptual baseline or very small log sizes |
| Hash Table (Last Timestamp) | O(1) average | O(n) | Best choice for real-time logging systems and interview solutions |