We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Logger Rate Limiter

Number: 359

Difficulty: Easy

Paid? Yes

Companies: Google, Atlassian, Netflix, Oracle, Intuit, Microsoft, Amazon, Reddit, AppFolio, Patreon

Problem Description

Design a logger system that receives a stream of messages with timestamps. For each unique message, it should be printed at most once every 10 seconds. That is, if a message is printed at timestamp t, the same message should not be printed again until t + 10. All messages arrive in chronological (non-decreasing) order.

Key Insights

  • Use a hash table (dictionary) to store the most recent timestamp when each message was printed.
  • Check if the current timestamp is at least 10 seconds later than the stored timestamp before printing the message.
  • The messages are in chronological order, so no need for extra data structures to handle reordering.
  • The approach efficiently handles streaming input with constant time lookups.

Space and Time Complexity

Time Complexity: O(1) average per message (dictionary lookup and update)
Space Complexity: O(n) in the worst case, where n is the number of unique messages

Solution

Maintain a hash table where keys are messages and values are the next allowed timestamp when the message can be printed. When a new message arrives with a given timestamp, check:

  1. If the message is not stored in the hash table, print it and set the allowed timestamp as current timestamp + 10.
  2. If the current timestamp is greater than or equal to the stored allowed timestamp, update the allowed timestamp and print the message.
  3. Otherwise, do not print the message. This approach is efficient because it only requires constant time operations per call and uses minimal additional space.

Code Solutions

# Python code with detailed comments

class Logger:
    def __init__(self):
        # Dictionary to record the next allowed timestamp for each message.
        self.message_dict = {}

    def shouldPrintMessage(self, timestamp: int, message: str) -> bool:
        # If message not seen before or current timestamp is >= expected timestamp.
        if message not in self.message_dict or timestamp >= self.message_dict[message]:
            # Update next allowed time to current timestamp + 10.
            self.message_dict[message] = timestamp + 10
            # Return True since message should be printed.
            return True
        # Else, the message cannot be printed yet.
        return False

# Example usage:
# logger = Logger()
# print(logger.shouldPrintMessage(1, "foo"))  # True
# print(logger.shouldPrintMessage(3, "foo"))  # False
← Back to All Questions