Logger Rate Limiter

Easy

3 views

Topics:

Arrays

Design a logger system that receives stream of messages along with its timestamps. Each message should be printed if and only if it is not printed in the last 10 seconds.

Given a message and a timestamp (in seconds granularity), return true if the message should be printed in the given timestamp, otherwise return false.

It is possible that several messages arrive roughly at the same time.

For example:

Logger logger = new Logger();

// logging string "foo" at timestamp 1
logger.shouldPrintMessage(1, "foo"); returns true;

// logging string "bar" at timestamp 2
logger.shouldPrintMessage(2,"bar"); returns true;

// logging string "foo" at timestamp 3
logger.shouldPrintMessage(3,"foo"); returns false;

// logging string "bar" at timestamp 8
logger.shouldPrintMessage(8,"bar"); returns false;

// logging string "foo" at timestamp 10
logger.shouldPrintMessage(10,"foo"); returns false;

// logging string "foo" at timestamp 11
logger.shouldPrintMessage(11,"foo"); returns true;

Constraints:

All timestamps are in the range [0, 10⁹].
Each message consists of lowercase English letters, and has length in the range [1, 30].
At most 10⁴ calls will be made to shouldPrintMessage.

Logger Rate Limiter

Easy

3 views

Topics:

Arrays

Design a logger system that receives stream of messages along with its timestamps. Each message should be printed if and only if it is not printed in the last 10 seconds.

Given a message and a timestamp (in seconds granularity), return true if the message should be printed in the given timestamp, otherwise return false.

It is possible that several messages arrive roughly at the same time.

For example:

Logger logger = new Logger();

// logging string "foo" at timestamp 1
logger.shouldPrintMessage(1, "foo"); returns true;

// logging string "bar" at timestamp 2
logger.shouldPrintMessage(2,"bar"); returns true;

// logging string "foo" at timestamp 3
logger.shouldPrintMessage(3,"foo"); returns false;

// logging string "bar" at timestamp 8
logger.shouldPrintMessage(8,"bar"); returns false;

// logging string "foo" at timestamp 10
logger.shouldPrintMessage(10,"foo"); returns false;

// logging string "foo" at timestamp 11
logger.shouldPrintMessage(11,"foo"); returns true;

Constraints:

All timestamps are in the range [0, 10⁹].
Each message consists of lowercase English letters, and has length in the range [1, 30].
At most 10⁴ calls will be made to shouldPrintMessage.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the expected range for the timestamp values and can I assume they are always non-negative and monotonically increasing for a given message?
How many unique messages can we expect to see, and what is the maximum length of a message string?
If two messages are received at the exact same timestamp, and the first one was printed, should the second one also be printed if it's a new message?
Should the logger implementation be thread-safe, or can I assume it will only be accessed from a single thread?
What should happen if a message is received with a timestamp earlier than one that has already been processed for that same message?

Brute Force Solution

Approach

The logger rate limiter problem asks us to only print a message if it hasn't been printed in the last ten seconds. The brute force method essentially remembers every message that has ever appeared and checks each new message against this complete history.

Here's how the algorithm would work step-by-step:

When a new message arrives, go through the entire list of previously seen messages.
For each previous message, check if it's the same as the new message and if it was printed within the last ten seconds.
If we find any previous message that matches and was printed recently, then don't print the new message and say it failed.
If we go through the entire list and don't find any recent duplicates, then print the new message and add it to the list of seen messages along with its timestamp.
The next time a message comes, repeat this entire process from the beginning.

Code Implementation

class Logger:

    def __init__(self):
        self.message_history = []

    def shouldPrintMessage(self, timestamp: int, message: str) -> bool:
        # Check against the entire history to enforce rate limiting
        for previous_timestamp, previous_message in self.message_history:
            if message == previous_message and timestamp - previous_timestamp < 10:
                return False

        # If no duplicates found, print and record the message
        self.message_history.append((timestamp, message))

        # Clean up old messages to save space.
        self.message_history = [(time, msg) for time, msg in self.message_history if timestamp - time < 10]

        return True

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

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(n²) – The described brute-force solution iterates through a list of previously seen messages for each new incoming message. In the worst case, every incoming message is unique, so the list of seen messages grows linearly with the number of incoming messages, 'n'. For each of the 'n' incoming messages, the algorithm iterates through the entire list of previously seen messages, which can grow to a length of up to 'n'. Therefore, we have nested iteration that results in approximately n*n operations. This leads to a time complexity of O(n²).

Space Complexity

O(N) – The brute force approach stores all previously seen messages and their timestamps. In the worst-case scenario, all N messages are unique and arrive at different times, requiring storage for each message and its timestamp. This results in an auxiliary list (or equivalent data structure) that grows linearly with the number of unique messages. Therefore, the auxiliary space complexity is O(N), where N is the number of unique messages received.

Optimal Solution

Approach

The key to solving the logger problem efficiently is to remember the last time a message was printed. We can then quickly check if a new message is allowed based on this stored information. This avoids unnecessary computations and makes the process very fast.

Here's how the algorithm would work step-by-step:

When a new message comes in, first check if we've seen it recently (within the last 10 seconds).
If we HAVE seen it recently, then the message should NOT be printed. It's being rate limited.
If we HAVE NOT seen the message recently, then the message should be printed.
After printing the message, remember the current timestamp for that message so we can check it later.
By keeping track of the last time each message was printed, we can quickly decide whether or not to print it without having to look at the entire history of messages.

Code Implementation

class Logger:

    def __init__(self):
        self.message_timestamps = {}

    def shouldPrintMessage(self, timestamp: int, message: str) -> bool:
        if message in self.message_timestamps:
            last_timestamp = self.message_timestamps[message]

            # Check if the message was printed within the last 10 seconds.
            if timestamp - last_timestamp < 10:
                return False

        # If the message is new or not recent, update the timestamp.
        self.message_timestamps[message] = timestamp

        # Store the current timestamp for the message.
        # Ensures we only print if it's a new message or outside the rate limit.
        return True

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(1) – The primary operation involves checking if a message exists in a hash map (or dictionary) and updating its timestamp. Hash map operations such as get and put have an average time complexity of O(1). Therefore, regardless of the number of messages processed, each individual message check and update takes constant time. Thus, the overall time complexity for processing a single message is O(1).

Space Complexity

O(N) – The algorithm uses a data structure (likely a hash map or dictionary) to store the last printed timestamp for each unique message. In the worst case, all N messages are unique, requiring storage for all of them. Therefore, the auxiliary space required grows linearly with the number of unique messages, N. This results in a space complexity of O(N).

Edge Cases

Case	How to Handle
Null or empty message	Treat an empty message as a valid, distinct message or reject it based on requirements; the important thing is to define the expected behavior.
Zero timestamp	Timestamp of 0 should be a valid timestamp and handled like any other timestamp (no special casing needed).
Very large timestamp values (potential for integer overflow)	Use a 64-bit integer to store the timestamps to avoid potential overflows, or use a different data type if necessary.
Messages arriving out of order (timestamp decreasing)	The problem doesn't explicitly forbid out-of-order timestamps, so ensure the solution correctly handles this case, potentially by not assuming increasing order.
Same message arriving multiple times within 10 seconds	The solution must correctly return false for subsequent calls with the same message within the 10-second window, utilizing the stored timestamp.
Different messages arriving at the same timestamp	Handle collisions by treating different messages at the same timestamp as separate events in the logger's message history.
Maximum number of unique messages being logged causing memory exhaustion	Consider a bounded cache to limit the memory usage; this could evict the oldest or least frequently used messages.
Negative timestamps	The problem doesn't explicitly state timestamps must be non-negative; either allow them or throw an exception based on the problem requirements.