359.Logger_Rate_Limiter(Easy).md

359. Logger Rate Limiter (Easy)

Date and Time: Oct 14, 2024, 18:04 (EST)

Link: https://leetcode.com/problems/logger-rate-limiter/

Question:

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 <= timestamp <= 10^9

• Every timestamp will be passed in non-decreasing order (chronological order).

• 1 <= message.length <= 30

• At most 10^4 calls will be made to shouldPrintMessage.

Walk-through:

We can just create a dict{} to keep track of each message with their valid_time = timestamp + 10. We check two scenarios: 1. message in self.dict, and we check if the time is valid so the message can be printed. 2. message not in self.dict, we add this message to dict{} and return True.

Follow-up: Think about we have infinite message coming, maybe just use heapq to maintain message that has valid time < timestamp.

Python Solution:

class Logger:

    def __init__(self):
        # Create a dict to keeping track
        self.dict = {}        

    def shouldPrintMessage(self, timestamp: int, message: str) -> bool:
        # Check if message in dict or not
        # If yes, we gonna check time: i. valid, update time, return True
        # ii. not valid time, return False
        # If message not in dict: add it and return True

        # TC: O(n), SC: O(n)
        if message in self.dict:
            if self.dict[message] <= timestamp:
                self.dict[message] = timestamp + 10
                return True
        elif message not in self.dict:
            self.dict[message] = timestamp + 10
            return True
        return False

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

Time Complexity: $O(n)$, n is how many messages we get.
Space Complexity: $O(n)$