Problem Description

You need to design a logger system that handles incoming messages with timestamps. The key requirement is that each unique message should only be printed at most once every 10 seconds.

Here's how the system works:

• When a message arrives at timestamp t and gets printed, any identical message that arrives within the next 10 seconds (before timestamp t + 10) should not be printed
• Messages always arrive in chronological order (timestamps are non-decreasing)
• Multiple messages can arrive at the same timestamp

You need to implement a Logger class with two methods:

1. Logger(): Initializes the logger object
2. shouldPrintMessage(timestamp, message): Takes a timestamp (integer) and a message (string) as input, and returns:
   • true if the message should be printed (either it's the first time seeing this message, or it's been at least 10 seconds since it was last printed)
   • false if the message should not be printed (it was printed less than 10 seconds ago)

For example:

• If message "foo" is printed at timestamp 1, it cannot be printed again until timestamp 11 or later
• If the same "foo" arrives at timestamps 2, 5, or 10, the method should return false
• If "foo" arrives at timestamp 11 or later, it can be printed again (method returns true)

The solution uses a hash map (limiter) to track each message and the earliest timestamp when it can be printed again. When a message should be printed, the map is updated with timestamp + 10 to block printing for the next 10 seconds.

Intuition

The core challenge is tracking when each message was last printed to determine if enough time has passed for it to be printed again. Since we need to check if at least 10 seconds have elapsed since the last print, we need to remember timing information for each unique message.

The natural approach is to use a hash map where:

• The key is the message string
• The value represents timing information

But what timing information should we store? We have two choices:

1. Store the timestamp when the message was last printed
2. Store the timestamp when the message can be printed again

The second option is more elegant because it simplifies our logic. Instead of storing the last print time and calculating last_print_time + 10 > current_timestamp each time, we directly store last_print_time + 10 as the "expiry time" or "next allowed time".

This way, our check becomes straightforward:

• If the current timestamp is less than the stored value, the message is still "blocked" → return false
• If the current timestamp is greater than or equal to the stored value (or the message doesn't exist in our map), the message can be printed → return true and update the map with current_timestamp + 10

The beauty of this approach is that we don't need to clean up old entries from the hash map. Since messages arrive in chronological order, old entries naturally become outdated and will always pass the timestamp check when encountered again. The map serves as a simple rate limiter that tracks the "cooling period" for each message.

Solution Approach

The solution uses a hash map-based approach to implement the rate limiting functionality. Let's walk through the implementation step by step:

Data Structure:

• We use a single hash map called limiter where:
  • Key: message string
  • Value: the earliest timestamp when this message can be printed again

Initialization:

def __init__(self):
    self.limiter = {}

We initialize an empty dictionary to store our message-timestamp mappings.

Core Logic in shouldPrintMessage:

1. Retrieve the stored timestamp for the message:

   t = self.limiter.get(message, 0)

   We use get(message, 0) which returns:

   • The stored timestamp if the message exists in the map
   • 0 as default if the message has never been seen before

2. Check if the message should be printed:

   if t > timestamp:
       return False

   If the stored "next allowed time" (t) is greater than the current timestamp, it means we're still within the 10-second blocking period, so we return False.

3. Update the map and return True:

   self.limiter[message] = timestamp + 10
   return True

   If we reach this point, the message can be printed. We:

   • Update the map with timestamp + 10 to block this message for the next 10 seconds
   • Return True to indicate the message should be printed

Why this works:

• For a new message: t = 0 is always less than any positive timestamp, so it passes the check
• For a repeated message: The stored value t represents when it can next be printed. If the current timestamp hasn't reached that point yet (timestamp < t), we block it
• The chronological order guarantee means we never have to handle cases where timestamps go backwards

Time and Space Complexity:

• Time: O(1) for each shouldPrintMessage call (hash map lookup and update)
• Space: O(M) where M is the number of unique messages seen so far

Example Walkthrough

Let's trace through a sequence of messages to see how the solution works:

Initial state: limiter = {} (empty hash map)

Message 1: shouldPrintMessage(1, "foo")

• Check: t = limiter.get("foo", 0) = 0
• Since 0 <= 1, the message can be printed
• Update: limiter["foo"] = 1 + 10 = 11
• Return: true
• State: limiter = {"foo": 11}

Message 2: shouldPrintMessage(2, "bar")

• Check: t = limiter.get("bar", 0) = 0
• Since 0 <= 2, the message can be printed
• Update: limiter["bar"] = 2 + 10 = 12
• Return: true
• State: limiter = {"foo": 11, "bar": 12}

Message 3: shouldPrintMessage(3, "foo")

• Check: t = limiter.get("foo", 0) = 11
• Since 11 > 3, the message is still blocked
• Return: false
• State: limiter = {"foo": 11, "bar": 12} (unchanged)

Message 4: shouldPrintMessage(8, "bar")

• Check: t = limiter.get("bar", 0) = 12
• Since 12 > 8, the message is still blocked
• Return: false
• State: limiter = {"foo": 11, "bar": 12} (unchanged)

Message 5: shouldPrintMessage(11, "foo")

• Check: t = limiter.get("foo", 0) = 11
• Since 11 <= 11, the message can be printed (exactly at the boundary)
• Update: limiter["foo"] = 11 + 10 = 21
• Return: true
• State: limiter = {"foo": 21, "bar": 12}

Message 6: shouldPrintMessage(12, "bar")

• Check: t = limiter.get("bar", 0) = 12
• Since 12 <= 12, the message can be printed
• Update: limiter["bar"] = 12 + 10 = 22
• Return: true
• State: limiter = {"foo": 21, "bar": 22}

The key insight is that we store the next allowed timestamp (current + 10) rather than the last printed timestamp. This makes our check simple: if the current timestamp is less than the stored value, the message is still in its "cooling period" and should be blocked.

Solution Implementation

Time and Space Complexity

Time Complexity: O(1) for the shouldPrintMessage method

• The dictionary get operation takes O(1) average time
• The dictionary assignment operation takes O(1) average time
• The comparison operation takes O(1) time
• All operations in the method are constant time, resulting in overall O(1) time complexity per call

Space Complexity: O(M) where M is the number of unique messages

• The limiter dictionary stores a timestamp for each unique message encountered
• In the worst case, if all messages are unique, the space grows linearly with the number of unique messages
• Each entry in the dictionary stores a message string as key and an integer timestamp as value
• The space complexity could also be expressed as O(N) where N is the total number of unique message strings stored over the lifetime of the Logger object

Common Pitfalls

1. Memory Leak with Unbounded Hash Map Growth

The Problem: The hash map grows indefinitely as new unique messages arrive, but old entries are never removed even when they're no longer relevant. In a production system running for extended periods, this could lead to memory exhaustion.

Example Scenario:

• System receives 1 million unique messages in the first hour
• After 10 seconds, these messages are eligible for reprinting but may never appear again
• The hash map still holds all 1 million entries indefinitely

Solution: Implement periodic cleanup or use a sliding window approach:

class Logger:
    def __init__(self):
        self.message_limiter = {}
        self.cleanup_interval = 100  # Clean up every 100 calls
        self.call_count = 0
  
    def shouldPrintMessage(self, timestamp: int, message: str) -> bool:
        # Periodic cleanup
        self.call_count += 1
        if self.call_count % self.cleanup_interval == 0:
            self._cleanup(timestamp)
      
        next_allowed_time = self.message_limiter.get(message, 0)
      
        if next_allowed_time > timestamp:
            return False
      
        self.message_limiter[message] = timestamp + 10
        return True
  
    def _cleanup(self, current_timestamp):
        # Remove entries that are expired (more than 10 seconds old)
        expired_messages = [msg for msg, time in self.message_limiter.items() 
                           if time <= current_timestamp]
        for msg in expired_messages:
            del self.message_limiter[msg]

2. Incorrect Handling of Edge Case: Same Timestamp

The Problem: Multiple identical messages arriving at the exact same timestamp might not be handled correctly if the logic isn't clear about whether only the first one should print.

Example:

• Message "foo" arrives at timestamp 5 (first occurrence) → should print
• Message "foo" arrives again at timestamp 5 → should NOT print

Solution: The current implementation handles this correctly, but ensure you understand why:

• First "foo" at t=5: Gets printed and sets limiter["foo"] = 15
• Second "foo" at t=5: Checks if 15 > 5 (true), so returns False

3. Integer Overflow in Long-Running Systems

The Problem: In systems running for very long periods, timestamp values could approach integer limits. Adding 10 to a near-maximum timestamp could cause overflow.

Solution: Use appropriate data types or implement overflow checking:

def shouldPrintMessage(self, timestamp: int, message: str) -> bool:
    next_allowed_time = self.message_limiter.get(message, 0)
  
    if next_allowed_time > timestamp:
        return False
  
    # Check for potential overflow
    import sys
    if timestamp > sys.maxsize - 10:
        # Handle overflow case - could reset or use modular arithmetic
        self.message_limiter[message] = 10  # Reset to small value
    else:
        self.message_limiter[message] = timestamp + 10
  
    return True

4. Concurrency Issues in Multi-threaded Environments

The Problem: If multiple threads call shouldPrintMessage simultaneously with the same message, race conditions could allow duplicate printing within the 10-second window.

Solution: Add thread synchronization:

import threading

class Logger:
    def __init__(self):
        self.message_limiter = {}
        self.lock = threading.Lock()
  
    def shouldPrintMessage(self, timestamp: int, message: str) -> bool:
        with self.lock:
            next_allowed_time = self.message_limiter.get(message, 0)
          
            if next_allowed_time > timestamp:
                return False
          
            self.message_limiter[message] = timestamp + 10
            return True