Logger Rate Limiter

LeetCode 359: Logger Rate Limiter Solution & Explanation

Problem Overview

TL;DR: The optimal solution utilizes a hash map to store the next allowed timestamp for each unique message, allowing for constant-time lookups and updates.

In the Logger Rate Limiter problem, we are tasked with designing a system that decides whether a specific log message should be printed based on its arrival time. The rule is strictly defined: a message can only be printed if it has not been printed in the last 10 seconds. If a message is printed at timestamp $t$, it cannot be printed again until timestamp $t + 10$.

This is a popular interview question found in LeetCode 359, often used by companies like Google and Amazon to test a candidate's ability to maintain state across method calls and design efficient data structures for stream processing.

Brute Force Approach for Logger Rate Limiter

A naive approach to solving the Logger Rate Limiter problem involves storing the entire history of printed messages and their timestamps in a list or array.

When shouldPrintMessage(timestamp, message) is called:

1. Iterate through the stored history of printed messages.
2. Check if the current message appears in the history.
3. If it appears, check the difference between the current timestamp and the recorded timestamp.
4. If the difference is less than 10, return false.
5. If the loop completes without finding a violation, add the new (timestamp, message) pair to the history and return true.

// Pseudo-code for Brute Force
List<Pair<int, string>> history

function shouldPrintMessage(timestamp, message):
    for each (t, msg) in history:
        if msg == message and timestamp - t < 10:
            return false
    
    history.add(timestamp, message)
    return true

Time Complexity: $O(N)$ per call, where $N$ is the number of previously printed messages. Over $N$ calls, this becomes $O(N^2)$. Space Complexity: $O(N)$ to store the history.

Why it fails: While this approach is correct logically, it is inefficient. As the system runs for a long time, the history grows indefinitely. Searching through thousands or millions of past logs for every single new message results in significant latency, likely causing a Time Limit Exceeded (TLE) error on larger datasets or failing system design latency requirements.

Algorithm Strategy: Design Patterns

We implement the Logger class using a Hash Map to persist state between function calls.

1. State Definition: A private Hash Map (Dictionary) named msg_map.
   • Key: The message string.
   • Value: The timestamp when this message is allowed to be printed again.
2. Constraint Enforcement:
   • When shouldPrintMessage(timestamp, message) is called, check if message exists in msg_map.
   • If it does not exist, it implies the message has never been printed (or at least not recently enough to matter). It is safe to print.
   • If it does exist, retrieve the allowed_timestamp.
3. Decision Logic:
   • If timestamp < allowed_timestamp: The rate limit is active. Return false.
   • If timestamp >= allowed_timestamp (or message is new): The rate limit has expired. Update msg_map[message] to timestamp + 10 and return true.

This strategy ensures that every call operates in constant time on average, satisfying the requirements for a high-throughput logging system.

Execution Flow

Let's trace the execution with an example sequence: [(1, "foo"), (2, "bar"), (3, "foo"), (8, "bar"), (10, "foo"), (11, "foo")].

1. Initialize: msg_map is empty {}.
2. Call (1, "foo"):
   • "foo" is not in msg_map.
   • Print is allowed.
   • Update msg_map: {"foo": 11} (1 + 10).
   • Return true.
3. Call (2, "bar"):
   • "bar" is not in msg_map.
   • Print is allowed.
   • Update msg_map: {"foo": 11, "bar": 12} (2 + 10).
   • Return true.
4. Call (3, "foo"):
   • "foo" is in msg_map with value 11.
   • Check: $3 < 11$. Condition fails.
   • Return false.
5. Call (8, "bar"):
   • "bar" is in msg_map with value 12.
   • Check: $8 < 12$. Condition fails.
   • Return false.
6. Call (10, "foo"):
   • "foo" is in msg_map with value 11.
   • Check: $10 < 11$. Condition fails.
   • Return false.
7. Call (11, "foo"):
   • "foo" is in msg_map with value 11.
   • Check: $11 \geq 11$. Condition passes.
   • Update msg_map: {"foo": 21, "bar": 12} (11 + 10).
   • Return true.

Proof of Correctness

The correctness relies on the invariant that msg_map[message] always stores the earliest time $T_{next}$ such that printing is allowed for all $t \geq T_{next}$.

1. Base Case: If a message has never been seen, it is printed immediately. We set $T_{next} = t_{current} + 10$. This correctly enforces the 10-second window.
2. Inductive Step: If a message is seen at $t_{current}$:
   • If $t_{current} < T_{next}$, the 10-second window from the previous print has not elapsed. We reject, maintaining the existing $T_{next}$.
   • If $t_{current} \geq T_{next}$, the window has elapsed. We print and establish a new window starting at $t_{current}$, setting $T_{next}' = t_{current} + 10$.

Since the timestamp inputs are non-decreasing, we do not need to handle out-of-order events, ensuring the simple comparison is always valid.

Pattern Reuse Notes

The Design pattern used here—maintaining state to enforce constraints—is applicable to several other high-frequency interview problems:

• LeetCode 146: LRU Cache: Requires designing a data structure (Hash Map + Doubly Linked List) to manage state with capacity constraints.
• LeetCode 155: Min Stack: Involves designing a stack that maintains auxiliary state (minimum values) alongside standard data.
• LeetCode 225: Implement Stack using Queues: Focuses on adapting one data structure's interface to satisfy another's contract.
• LeetCode 232: Implement Queue using Stacks: Similar to the above, requiring state manipulation to reverse order efficiently.

Understanding how to map inputs to state identifiers is the key to solving these design-centric problems.

Reference Implementation

C++ Solution for LeetCode 359

1#include <unordered_map>
2#include <string>
3
4class Logger {
5private:
6    // Map to store the message and the next allowed timestamp
7    std::unordered_map<std::string, int> msg_map;
8
9public:
10    Logger() {
11        // Initialization is handled by the container
12    }
13    
14    bool shouldPrintMessage(int timestamp, std::string message) {
15        // Check if message exists in map
16        if (msg_map.find(message) == msg_map.end()) {
17            // New message, update allowed time and return true
18            msg_map[message] = timestamp + 10;
19            return true;
20        }
21        
22        // Message exists, check if current timestamp is valid
23        if (timestamp >= msg_map[message]) {
24            // Update the next allowed timestamp
25            msg_map[message] = timestamp + 10;
26            return true;
27        }
28        
29        // Message arrived too soon
30        return false;
31    }
32};

Java Solution for LeetCode 359

1import java.util.HashMap;
2import java.util.Map;
3
4class Logger {
5    // Map to store the message and the next allowed timestamp
6    private Map<String, Integer> msgMap;
7
8    public Logger() {
9        msgMap = new HashMap<>();
10    }
11    
12    public boolean shouldPrintMessage(int timestamp, String message) {
13        // Check if the message is in the map
14        if (!msgMap.containsKey(message)) {
15            msgMap.put(message, timestamp + 10);
16            return true;
17        }
18        
19        // Retrieve the next allowed timestamp
20        int allowedTime = msgMap.get(message);
21        
22        if (timestamp >= allowedTime) {
23            // Update the allowed timestamp for future calls
24            msgMap.put(message, timestamp + 10);
25            return true;
26        }
27        
28        // Rate limit active
29        return false;
30    }
31}

Python Solution for LeetCode 359

1class Logger:
2
3    def __init__(self):
4        # Dictionary to store message -> next_allowed_timestamp
5        self.msg_map = {}
6
7    def shouldPrintMessage(self, timestamp: int, message: str) -> bool:
8        # If message not in map, or current time is past the allowed time
9        if message not in self.msg_map or timestamp >= self.msg_map[message]:
10            # Update the next allowed time to current + 10
11            self.msg_map[message] = timestamp + 10
12            return True
13        
14        # If we are here, the message is being printed too frequently
15        return False