Message Rate Limiter

Problem Statement

You are tasked with building a message rate limiter for a distributed logging service. The system receives a sequence of log messages accompanied by integer timestamps in non-decreasing order.

Design a class MessageLimiter with the following requirements:

• The constructor initializes the rate limiter with a given time_window (in seconds).
• A method should_accept_message(timestamp: int, message: str) -> bool checks whether the incoming message should be accepted or dropped.
• A message is accepted (True) if it has never been seen before, or if at least time_window seconds have passed since the last accepted occurrence of that exact message string.
• When a message is accepted, its cooldown period resets starting from timestamp.
• If a message is rejected (False), its timestamp is ignored, and the cooldown does not reset.

Class Interface

class MessageLimiter:
    def __init__(self, time_window: int = 10):
        """Initialize your data structure here."""
        pass

    def should_accept_message(self, timestamp: int, message: str) -> bool:
        """Returns True if the message should be accepted, False otherwise."""
        pass

Examples

Example 1

limiter = MessageLimiter(time_window=10)

limiter.should_accept_message(1, "foo")   # Returns True (next allowed at >= 11)
limiter.should_accept_message(2, "bar")   # Returns True (next allowed at >= 12)
limiter.should_accept_message(3, "foo")   # Returns False (dropped; last accepted remains 1)
limiter.should_accept_message(8, "bar")   # Returns False (dropped; last accepted remains 2)
limiter.should_accept_message(10, "foo")  # Returns False (dropped; 10 = 1 + 10; next allowed at >= 21)

Constraints

• 1 <= time_window <= 10^6
• 0 <= timestamp <= 10^9
• Timestamps in successive calls are strictly non-decreasing: timestamp_{i} <= timestamp_{i+1}.
• 1 <= len(message) <= 50
• At most 10^5 calls will be made to should_accept_message.

Edge Cases

• Multiple different messages arriving at the exact same timestamp.
• The same message arriving multiple times within the cooldown window (none of the dropped occurrences should extend the cooldown).