LeetCode 359: Logger Rate Limiter Solution
LeetCode 359, Logger Rate Limiter, asks you to build a logger that prints each unique message at most once every 10 seconds. A repeat inside that window is dropped.
One method does the work. shouldPrintMessage(timestamp, message) returns true if the message should print now, and false if it is too soon.
The problem
Timestamps arrive in seconds and never go backwards. Two calls can share the same second.
A message may print again once 10 or more seconds have passed since its last print. Exactly 10 seconds counts as allowed.
Different messages never block each other. The window is tracked per message, not for the logger as a whole.
Example
| Call | Result | Reason |
|---|---|---|
| shouldPrintMessage(1, "foo") | true | First time seen. |
| shouldPrintMessage(2, "bar") | true | First time seen. |
| shouldPrintMessage(3, "foo") | false | Only 2 seconds since "foo" printed. |
| shouldPrintMessage(8, "bar") | false | Only 6 seconds since "bar" printed. |
| shouldPrintMessage(10, "foo") | false | Only 9 seconds since "foo" printed. |
| shouldPrintMessage(11, "foo") | true | A full 10 seconds have passed. |
Constraints
- The timestamp is between 0 and 10 to the power of 9.
- Timestamps are passed in non-decreasing order.
- Each message has 1 to 30 characters.
- At most 10,000 calls are made.
Approach 1: a hash map of last print times
Keep a map from each message to the second it last printed.
On a call, look the message up. If the map has no entry, print it and store the timestamp.
If an entry exists, subtract. When timestamp - last is under 10, return false and change nothing stored.
Otherwise store the new timestamp and return true. A hash map answers each call in constant time on average.
The Python code above keeps a dictionary called last_print. Each key is a message and each value is the second that message last printed.
One detail decides whether the solution passes.
The stored time is updated only when the message actually prints. If you update it on every call, a message repeated every second would never print again.
That is the most common bug in this question. The window starts at the last print, not at the last attempt.
Java, approach 1
The Java version uses a HashMap<String, Integer>. It follows the same three steps as the Python version.
A missing key means the message has never printed. containsKey handles that case before any subtraction runs.
Space is O(m), where m is the number of distinct messages ever seen. Nothing is removed, so the map only grows.
For this question that is fine, because at most 10,000 calls are made. For a logger running for months it is not. That limitation leads to the second approach.
Approach 2: a queue plus a set
This version stores only the messages still inside the 10-second window. Memory then depends on current traffic, not on history.
Keep a queue of timestamp and message pairs in arrival order. Keep a set holding the same messages for fast lookup.
On each call, first remove every pair at the front of the queue whose timestamp is 10 or more seconds old. Remove each of those messages from the set as well.
Then check the set. If the message is present, return false.
If it is absent, add it to the queue and to the set, then return true.
Python, approach 2
The Python code above uses collections.deque for the queue and a plain set for lookup.
The purge loop runs before the membership check. Without it, an expired entry would block a message that should print.
The set exists only for speed. Scanning the queue would give the same answer, but each call would cost O(k) instead of O(1).
Each pair enters the queue once and leaves it once. Averaged over many calls, the cost is constant.
Java, approach 2
The Java version uses an ArrayDeque for the queue and a HashSet for lookup. A small pair class holds the timestamp and the message together.
An int[] of length two plus a parallel list of strings works just as well if you prefer no extra class.
Cost of each approach
| Approach | Time per call | Extra space |
|---|---|---|
| Hash map | O(1) on average | O(m), every distinct message ever seen |
| Queue plus set | O(1) averaged over calls | O(k), messages inside the last 10 seconds |
One call in approach 2 can be slow. If many entries expire at the same moment, that single call removes all of them.
The average stays constant, because each entry is removed exactly once across the whole run.
Which one to give in an interview
Give the hash map first. It is shorter, it is what the question expects, and it is easier to get right under time pressure.
Then say that the map never forgets a message, so memory grows with the number of distinct messages. Offer the queue version as the fix.
Naming that trade-off is what turns a correct answer into a strong one.
Edge cases to check
- Two calls in the same second with the same message. The second one returns false.
- A gap of exactly 10 seconds. It returns true, because the rule is "at least 10".
- Two different messages at the same timestamp. Both return true.
- A long run of one message. Only the first call in each window prints.
- Many threads calling at once. The question is single threaded, but say how you would lock the map if asked.
How to Prepare
- Learn the design-a-class pattern. These questions give you a class and a few methods, and the whole answer is the data structure you pick.
- Solve the near neighbours. 362. Design Hit Counter and 346. Moving Average from Data Stream use the same sliding window idea.
- Then do the harder one. 146. LRU Cache combines a hash map with a linked list.
- Study the patterns as a group. Grokking the Coding Interview covers sliding window and hash map problems in one place.
- Practice saying the cost out loud. A mock interview forces you to state time and space before you write code.
GET YOUR FREE
Coding Questions Catalog
$123
$197
$72
