Domain 1EasyCORE

Logger Rate Limiter

The problem requires designing a logger system that processes messages with timestamps. Each unique message should only be printed at most once every 10 seconds. The input consists of method calls to `shouldPrintMessage` with a timestamp and a message string. The output is a boolean indicating whether the message should be printed at the given timestamp.

Domain: Easy•Updated: 2026-08-31
#Algorithms#LeetCode#qwen2.5-coder:14b#Hash Table#Design

359. Logger Rate Limiter

Model: qwen2.5-coder:14b
Topics: Hash Table,Design
FAANG asked: 1
Acceptance rate: 72.5%


Problem Breakdown

The problem requires designing a logger system that processes messages with timestamps. Each unique message should only be printed at most once every 10 seconds. The input consists of method calls to shouldPrintMessage with a timestamp and a message string. The output is a boolean indicating whether the message should be printed at the given timestamp.

Inputs:

  • timestamp: An integer representing the time when the message arrives.
  • message: A string representing the message content.

Outputs:

  • A boolean value (true or false) indicating whether the message should be printed.

Implicit Constraints:

  • Messages arrive in chronological order.
  • The timestamp range is from 0 to (10^9).
  • Message length ranges from 1 to 30 characters.
  • There can be up to (10^4) calls to shouldPrintMessage.

Intuition

A brute-force approach would involve storing all messages and their timestamps, checking each message against the current timestamp every time a new message arrives. This approach is inefficient in terms of both time and space complexity.

The key insight is to use a hash table (dictionary) to store the last printed timestamp for each message. This allows us to quickly check if a message should be printed by comparing the current timestamp with the stored timestamp plus 10 seconds.

Approach

  1. Data Structure Choice: Use a dictionary (self.log) where keys are messages and values are their most recent timestamps.
  2. Initialization: The Logger class initializes an empty dictionary.
  3. Method Implementation:
    • If the message is not in the dictionary, add it with the current timestamp and return true.
    • If the message is in the dictionary, check if the difference between the current timestamp and the stored timestamp is at least 10 seconds.
      • If yes, update the timestamp and return true.
      • If no, return false.

Complexity Analysis

  • Time Complexity: (O(1)) for each call to shouldPrintMessage because dictionary operations (insertion and lookup) are average (O(1)).
  • Space Complexity: (O(M)), where (M) is the number of unique messages stored in the dictionary.

Solution

class Logger:

    def __init__(self):
        # Initialize a dictionary to store message and its last printed timestamp
        self.log = {}

    def shouldPrintMessage(self, timestamp: int, message: str) -> bool:
        # If the message is not in the log or the time difference is at least 10 seconds
        if message not in self.log or timestamp - self.log[message] >= 10:
            # Update the timestamp for this message
            self.log[message] = timestamp
            return True
        else:
            return False

Edge Cases Handled

  • First Message: If a message is received for the first time, it will always be printed.
  • Messages with Same Timestamp: Multiple messages can arrive at the same timestamp. The dictionary ensures that only one of them is printed if they are unique.
  • Messages Repeated After 10 Seconds: A message that was not printed due to being within 10 seconds of its last print will be allowed after exactly 10 seconds have passed.
  • Large Timestamps: The use of integer timestamps ensures that the solution works efficiently even with large values up to (10^9).