359. Logger Rate Limiter

Problem¶

Implement Logger.shouldPrintMessage(timestamp, message): accept a message only if it has never been accepted or at least 10 seconds have elapsed since its last acceptance. Timestamps are non-decreasing.

Calls:   (1, "foo")  (2, "bar")  (3, "foo")  (10, "foo")  (11, "foo")
Returns: True        True        False       False        True

class Logger:
    def __init__(self):
        pass

    def shouldPrintMessage(self, timestamp: int, message: str) -> bool:
        pass

Key trick¶

Store each message's next allowed timestamp in a dictionary; update it only when accepting the message.

Trap¶

Rejected messages must not restart the cooldown, and exactly 10 seconds later is allowed. Different messages have independent cooldowns.

Why is it interesting?¶

It tests stateful API design: choosing the right stored state makes each decision a single lookup.

Python solution¶

class Logger:
    def __init__(self):
        self.next_allowed = {}

    def shouldPrintMessage(self, timestamp: int, message: str) -> bool:
        if timestamp < self.next_allowed.get(message, 0):
            return False
        self.next_allowed[message] = timestamp + 10
        return True

Time: Expected \(O(1)\) per call, with message length bounded by 30.

Space: \(O(u)\), where \(u\) is the number of distinct messages seen.

Comment on my solution¶

Your algorithm and boundary check are correct. The assignment self.msgs.get[message] raises TypeError because get is a method; assign directly to the dictionary:

self.msgs[message] = timestamp + 10

Adding the return annotation -> bool also makes the interface clearer.

# Ideas:
# - keep msg -> next_allowed_timestamp in a map
#   - map is updated when the msg sent should be printed

# WRONG
class Logger:
    def __init__(self):
        self.msgs = {}

    def shouldPrintMessage(self, timestamp: int, message: str):
        if timestamp >= self.msgs.get(message, 0):
            self.msgs.get[message] = timestamp + 10
            return True
        return False

Extra¶

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 <= 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.