359. Logger Rate Limiter - Detailed Explanation

Problem Statement

Design a logger system that receives a stream of messages with timestamps and prints each unique message at most once every 10 seconds. In other words, if a message has been printed in the last 10 seconds, any new occurrences of that same message should be throttled (ignored). If 10 seconds or more have elapsed since it was last printed, the message can be printed again.

• Input: A series of calls to logger.shouldPrintMessage(timestamp, message) where timestamp is in seconds (non-decreasing order) and message is a string (lowercase English letters).
• Output: Each call returns true if the message should be printed at that timestamp (not printed in the last 10 seconds), or false if it should be skipped due to the rate limit.

Why? This ensures no duplicate message is printed too frequently. You can imagine it like hearing someone shout “Hey!” at a party – you only respond if at least 10 seconds have passed since the last identical shout. If they repeat sooner, you ignore them.

Example

Suppose the logger receives the following calls in order:

logger.shouldPrintMessage(1, "hello") ➞ true  
logger.shouldPrintMessage(2, "world") ➞ true  
logger.shouldPrintMessage(3, "hello") ➞ false  
logger.shouldPrintMessage(11, "hello") ➞ true  

Explanation:

• At timestamp 1, message "hello" has not been seen before, so it prints (true).
• At timestamp 2, message "world" is new, so it prints (true).
• At timestamp 3, message "hello" appears again only 2 seconds after it was last printed. Since 2 < 10 seconds, it is throttled (false).
• At timestamp 11, message "hello" appears again. Now 10 seconds have passed since it was last printed at t=1, so it can print again (true).

This meets the requirement that “hello” was printed at most once in any 10-second window.

Key Points and Constraints

• Timestamps are non-decreasing (they won’t go backward, but can be equal or increase).
• Each message is a lowercase string up to 30 characters.
• Timestamps can range from 0 up to 10^9.
• We need efficient performance for potentially many calls. Each shouldPrintMessage call should be fast (ideally O(1) time).
• We must ensure we don’t use excessive memory (avoid storing unnecessary or expired data).

Hints to Solve the Problem:

1. Use a data structure to remember the last time each message was printed. This structure should allow quick checks and updates. A hash map (dictionary) is ideal for direct lookups by message.

2. On each new message event, check the stored timestamp for that message (if any). Compute the time difference with the current timestamp.

3. If the message was printed in the past 10 seconds (difference < 10), return false (skip it).

4. Otherwise (message is new or it’s been ≥10 seconds since last print), update the stored timestamp to the current time and return true.

5. Optionally, consider cleaning up or limiting stored data. Since timestamps grow and messages may stop coming, think about removing old entries if they are no longer needed (especially in certain approach).

With these ideas in mind, let's explore two approaches: one using a HashMap and another using a Queue.

Approach 1: Using a HashMap (Optimal Solution)

Idea: Maintain a hash map (dictionary) where keys are message strings and values are the last timestamp at which that message was printed. This way, whenever a message comes in, we can instantly check when it was last seen.

• When a new message arrives: look up its last printed timestamp in the map.
  • If the message is not in the map (never seen before), we can print it. Store the current timestamp in the map for that message.
  • If it exists in the map, calculate the difference: current_timestamp - last_timestamp.
    • If this difference is less than 10, it means the last print was within the past 10 seconds – so we return false (do not print again yet).
    • If the difference is ≥ 10 seconds, we return true and update the map with the new timestamp (meaning we print it now and reset the 10-second window).

This approach directly enforces the rule by always keeping track of the most recent print time for each message. It uses O(1) time on average for each check since hash map operations (get/put) are constant time. It’s also space-efficient, storing at most one entry per unique message.

Why this is optimal: We only store necessary data (one timestamp per message) and each message check/update is constant time. There’s no need to iterate over other messages or timestamps when processing a new message. This satisfies the efficiency requirements even if there are many calls.

Potential drawback: The map can grow if there are many unique messages over time and we never remove old ones. In a long-running system, if messages stop appearing, their timestamps might remain stored. However, since each entry is small (just an integer timestamp) and the problem constraints don’t demand removal of stale data, this is usually acceptable. If needed, a periodic cleanup of very old entries could be implemented, but it’s not required for correctness.

Approach 1 – Example Walkthrough:

Using the earlier example, let’s see how the HashMap evolves and how decisions are made:

• Start: map is empty {}.
• t=1, "hello": Not in map, so allow print. Update map: {"hello": 1}.
• t=2, "world": Not in map, allow print. Update map: {"hello": 1, "world": 2}.
• t=3, "hello": Map says "hello" last seen at 1. Difference = 3-1 = 2, which is < 10, so deny print (false). (Map remains {"hello": 1, "world": 2} unchanged since we didn’t print.)
• t=11, "hello": Last seen at 1. Difference = 11-1 = 10, which is >= 10, so allow print (true). Update map: {"hello": 11, "world": 2} (now “hello”’s last print time is 11).

At the end, the map tells us “hello” was last printed at 11 and “world” at 2. This matches the rule that “hello” was printed at t=1 and t=11, but not in between.

Why not just use a Set or List?

We need to know when the message was last printed, not just that it was printed. A set of messages wouldn’t tell us how recently it was printed. A list of past messages would let us check the last occurrence, but finding that last occurrence for each message would be inefficient (linear search). A map directly gives the last occurrence time in O(1) time, making it the best choice for this task.

Approach 2: Using a Queue (Alternative Approach)

Idea: An alternative is to use a queue to keep track of messages in the last 10-second window, coupled with a set for quick lookup. This approach explicitly maintains the sliding window of recent messages:

• Use a queue of pairs (timestamp, message) representing messages that have been printed and are still within the last 10 seconds window. New messages get added to the back of the queue when printed.
• Use a set of messages currently in that queue (the messages printed in the last 10 seconds). This allows us to quickly check if a new message is a duplicate of something in the recent window.

When a new message arrives:

1. Evict old messages: First, we remove any entries from the front of the queue that are older than 10 seconds compared to the current timestamp. For each removed entry, also remove that message from the set. This ensures the queue/set only contain messages from the last <10 seconds. (If current time is t, pop from queue while current_t - front_of_queue.timestamp >= 10.).

2. After cleaning, check if the incoming message is in the set of recent messages.

   • If yes, that means the message was printed within the last 10 seconds (still in our queue window), so we return false (throttle it).
   • If no, then it’s not a duplicate in the last 10 seconds. We can print it: push (timestamp, message) onto the queue and add the message to the set, then return true.

This approach achieves the same outcome as the hash map: the set ensures no message repeats in a 10-second span, and the queue automatically drops messages once they exit the 10-second window. The logic is a bit more involved, but it has a nice side effect of naturally cleaning up old messages (so the data structure doesn’t grow without bound). At any time, the queue contains at most 10 seconds worth of messages. In the worst case, if messages are very frequent, the queue size could be proportional to all messages in a 10-second span.

Efficiency: Checking and adding to a set is O(1) average. Removing old messages from the queue is also typically O(1) per message (each message enters and leaves the queue at most once). In the average case, each incoming message triggers a constant amount of work (amortized O(1) time per message). In the worst case, if many messages expire at once, a single call might clean up multiple old entries, making that call O(n) where n is the number of messages in the 10-second window. Overall, if there are N messages total, each message is enqueued and dequeued once, so the total work is O(N) (which averages to O(1) per message). Space usage is O(N) in worst case (if many unique messages within 10 seconds).

Approach 2 – Example Walkthrough:

Let’s walk through the same example using the queue-set approach to visualize how it works:

• Start: queue is empty [], set is empty {}.
• t=1, "hello": Clean-up step: queue empty (nothing to remove). "hello" not in set, so we print it. Enqueue (1,"hello"), set becomes {"hello"}.
• t=2, "world": Clean-up: front of queue is (1,"hello"). Check age: 2-1 = 1 < 10, so nothing removed. "world" not in set, print it. Enqueue (2,"world"), set becomes {"hello","world"}.
• t=3, "hello": Clean-up: front (1,"hello"), 3-1=2 < 10, nothing removed (still within window). Now check "hello" – it is in the set ("hello" was printed at t=1 which is still within 10s). So we do NOT print. (Queue and set remain unchanged: still [(1,"hello"), (2,"world")] and {"hello","world"}.)
• t=11, "hello": Clean-up: front (1,"hello"), 11-1=10, which is >=10, so remove (1,"hello") from queue and remove "hello" from set. Now front is (2,"world"): 11-2=9 < 10, stop removing. After cleanup, queue contains [(2,"world")], set is {"world"}. Now check "hello" – it’s no longer in the set (we just removed the old occurrence). Therefore, it’s allowed to print. Enqueue (11,"hello"), set becomes {"world","hello"}. Return true.

The results (true, true, false, true) match the requirements. The queue approach ensures that at t=11, the old "hello" from t=1 was purged, so the new "hello" is treated as fresh.

Code Implementations

Python – Approach 1 (Using Dictionary)