Logger Rate Limiter
Last Updated: March 29, 2026
Understanding the Problem
We are building a rate limiter for log messages. When a message arrives, we need to decide: has this exact message been printed within the last 10 seconds? If yes, suppress it. If no (or we have never seen it), print it and record the timestamp.
The important detail is the 10-second window. If "foo" was last printed at time 1, it can be printed again at time 11 or later, but not at time 10. The check is currentTimestamp >= lastTimestamp + 10, or equivalently, currentTimestamp - lastTimestamp >= 10.
Since messages arrive in chronological order, we never need to worry about a message arriving "in the past." This simplifies things because we can safely overwrite timestamps without corrupting earlier decisions.
The key observation: we need fast lookups by message string and we need to store the most recent print timestamp for each message. A hash map is the natural fit.
Key Constraints:
0 <= timestamp <= 10^9-- Timestamps can be very large, but we only store one per unique message, so this does not affect space much. We just need to compare two integers.- Every
timestampis non-decreasing -- We never receive out-of-order messages. This means we do not need to handle retroactive changes to the rate limit window. 1 <= message.length <= 30-- Messages are short strings. Hashing them is fast and collisions are unlikely.- At most
10^4calls -- Even an O(n) approach per call would give us at most 10^8 operations. But we can easily do O(1) per call with a hash map.
Approach 1: Brute Force (Store All Messages with Timestamps)
Intuition
The most straightforward approach: store every (timestamp, message) pair that was printed. When a new message arrives, scan through all stored pairs to find if the same message was printed within the last 10 seconds.
This works, but it is clearly wasteful. We are storing every printed message-timestamp pair, even though we only care about the most recent occurrence of each message. And we are scanning the entire history on every call.
Algorithm
- Initialize an empty list to store (timestamp, message) pairs.
- On each
shouldPrintMessage(timestamp, message)call: - Scan the list backward looking for the same message.
- If found with a timestamp within the last 10 seconds (i.e.,
timestamp - foundTimestamp < 10), return false. - If not found within 10 seconds (or not found at all), add the pair to the list and return true.
Example Walkthrough
Input:
For each call, we scan the entire list of previously printed messages backward to find a match. If found within 10 seconds, reject. Otherwise, add and allow.
Output:
Code
- Time Complexity: O(n) per call, where n is the number of messages printed so far. In the worst case, we scan through all stored pairs before finding a match or reaching the beginning.
- Space Complexity: O(n) where n is the total number of printed messages. We never remove old entries, so the list grows forever.
This approach works but is wasteful. We are doing a linear search when we only need the last print time for a specific message. What if we used a data structure that lets us jump directly to a message's last print time in O(1)?
Approach 2: Hash Map (Optimal)
Intuition
Instead of scanning a list, we use a hash map where the key is the message string and the value is the next allowed timestamp for that message. When a message arrives at time t, we check: is t at least the stored next-allowed time? If the message is not in the map at all, it has never been printed, so we allow it.
When we allow a message, we set its next-allowed timestamp to t + 10. This way, future calls just need a single map lookup and a single comparison. No scanning, no history.
This is the classic rate limiter pattern: store the "cooldown expiry" rather than the "last seen time." It is slightly cleaner because the check becomes timestamp >= map.get(message) instead of timestamp - map.get(message) >= 10, though both are equivalent.
The hash map acts as a "memory" for the rate limiter. By storing the next allowed timestamp (instead of the last printed timestamp), we simplify the check to a single comparison: is the current time at or past the expiry? This is the same pattern used in real-world rate limiters, token buckets, and caching systems, where you store the expiry time rather than computing it on every check.
The approach is correct because messages arrive in chronological order. If we update the next-allowed time for a message, no future call will have a smaller timestamp that could invalidate our decision. This ordering guarantee is what makes the simple hash map sufficient.
Algorithm
- Initialize an empty hash map that maps message strings to their next allowed timestamp.
- On each
shouldPrintMessage(timestamp, message)call: - Look up the message in the map.
- If the message exists and
timestamp < nextAllowed, return false (still in cooldown). - Otherwise, update the map: set
map[message] = timestamp + 10. - Return true.
Example Walkthrough
Code
- Time Complexity: O(1) per call. Hash map lookup, comparison, and insertion are all O(1) amortized. String hashing for messages up to length 30 is effectively constant.
- Space Complexity: O(n) where n is the number of unique messages. We store one entry per unique message string. Since there are at most 10^4 calls, the map holds at most 10^4 entries.