Problem Informations

• Problem Index: 359
• Problem Link: Logger Rate Limiter
• Topics: Hash Table, Design, Data Stream

Problem Description

Design a logger system that receives a stream of messages along with their timestamps. Each unique message should only be printed at most every 10 seconds (i.e. a message printed at timestamp $t$ will prevent other identical messages from being printed until timestamp $t + 10$).

All messages will come in chronological order. Several messages may arrive at the same timestamp.

Implement the Logger class:

• Logger(): Initializes the logger object.
• bool shouldPrintMessage(int timestamp, string message): Returns true if the message should be printed in the given timestamp, otherwise returns false.

Example 1:

Input

["Logger", "shouldPrintMessage", "shouldPrintMessage", "shouldPrintMessage", "shouldPrintMessage", "shouldPrintMessage", "shouldPrintMessage"]
[[], [1, "foo"], [2, "bar"], [3, "foo"], [8, "bar"], [10, "foo"], [11, "foo"]]

Output

[null, true, true, false, false, false, true]

Explanation

Logger logger = new Logger();
logger.shouldPrintMessage(1, "foo");  // return true, next allowed timestamp for "foo" is 1 + 10 = 11
logger.shouldPrintMessage(2, "bar");  // return true, next allowed timestamp for "bar" is 2 + 10 = 12
logger.shouldPrintMessage(3, "foo");  // 3 < 11, return false
logger.shouldPrintMessage(8, "bar");  // 8 < 12, return false
logger.shouldPrintMessage(10, "foo"); // 10 < 11, return false
logger.shouldPrintMessage(11, "foo"); // 11 >= 11, return true, next allowed timestamp for "foo" is 11 + 10 = 21

Constraints:

• $0 \leq \text{timestamp} \leq 10^9$
• Every timestamp will be passed in non-decreasing order (chronological order).
• $1 \leq \text{message.length} \leq 30$
• At most $10^4$ calls will be made to shouldPrintMessage.

Intuition

The problem requires designing a system that controls the frequency of message logging to prevent duplicate messages from being printed within a short span of time (10 seconds in this case). The challenge is to efficiently manage the timestamps of messages such that each identical message is not printed if it repeats within 10 seconds from its last print. The solution should efficiently track and update the logging timestamps and determine if a message can be printed at a given timestamp.

Approach

The approach to solving the problem involves utilizing a hash table (unordered_map in C++) to maintain the last printed timestamp for each unique message. This allows for constant time complexity operations for inserting, updating, and querying the timestamps associated with these messages.

1. Initialization:

   • An unordered map named messageLastPrintedTime is used as the hash table to store the last logged timestamp for each unique message as the key.

2. Logging Check:

   • For each incoming message with a specific timestamp, the system checks if the message exists in the hash table. If it exists, the system further checks if the message’s last log time (retrieved from the hash table) is within a 10-second window from the current timestamp. If it is within the 10-second window, the message should not be printed, and the function returns false.
   • If the message does not exist in the hash table or its last log time is outside the 10-second window, it is permissible to log the message.

3. Updating Timestamp:

   • Once it is determined that a message can be printed, the hash table is updated with the current timestamp as the new last printed time for that message.
   • The function then returns true, indicating the message was successfully printed.

By utilizing a hash table for rapid updates and checks, the system ensures efficient handling of up to $10^4$ calls as per the constraints, maintaining optimal performance in both time and space complexity.

Code

C++

class Logger {
private:
    // A hash table to store the last printed time of each message
    unordered_map<string, int> messageLastPrintedTime;

public:
    // Constructor to initialize the Logger object
    Logger() {
        // Clear the hash table when the Logger object is created
        messageLastPrintedTime.clear();
    }
    
    // Function to check if a message should be printed at the given timestamp
    bool shouldPrintMessage(int timestamp, string message) {
        // Check if the message exists in the hash table and if it's within the 10-second window
        if (messageLastPrintedTime.find(message) != messageLastPrintedTime.end() 
            && messageLastPrintedTime[message] > timestamp - 10) {
            return false;
        }

        // Update the last printed time for the message to the current timestamp
        messageLastPrintedTime[message] = timestamp;

        // Allow the message to be printed
        return true;
    }
};

/**
 * Your Logger object will be instantiated and called as such:
 * Logger* obj = new Logger();
 * bool param_1 = obj->shouldPrintMessage(timestamp, message);
 */

Python

class Logger:
    # A hash table to store the last printed time of each message
    def __init__(self):
        # Clear the hash table when the Logger object is created
        self.messageLastPrintedTime = {}

    # Function to check if a message should be printed at the given timestamp
    def shouldPrintMessage(self, timestamp: int, message: str) -> bool:
        # Check if the message exists in the hash table and if it's within the 10-second window
        if message in self.messageLastPrintedTime and self.messageLastPrintedTime[message] > timestamp - 10:
            return False

        # Update the last printed time for the message to the current timestamp
        self.messageLastPrintedTime[message] = timestamp

        # Allow the message to be printed
        return True

# Your Logger object will be instantiated and called as such:
# obj = Logger()
# param_1 = obj.shouldPrintMessage(timestamp, message)

Complexity

• Time complexity: The time complexity of the shouldPrintMessage function is $O(1)$. This is because both the lookup and insertion operations in an unordered_map (hash table) have an average time complexity of $O(1)$. Thus, checking if a message exists and updating the message timestamp both execute in constant time.

• Space complexity: The space complexity is $O(m)$, where $m$ is the number of unique messages passed to the shouldPrintMessage function. This space is used to store the mapping of each unique message to its last printed timestamp in the unordered_map. In the worst-case scenario, every call to shouldPrintMessage could be for a unique message, resulting in space complexity proportional to the number of unique messages.