Problem Description

The Logger Rate Limiter problem asks you to design a logger system that receives a stream of messages along with their timestamps. Each message is a string, and each timestamp is an integer representing seconds since the epoch. The logger should decide whether a message should be printed based on the following rule:

• Each message can be printed only if it has not been printed in the last 10 seconds (including the current timestamp).
• If a message arrives and it was printed less than 10 seconds ago, it should not be printed again.

You are to implement a class Logger with the following methods:

• Logger(): Initializes the logger object.
• bool shouldPrintMessage(int timestamp, string message): Returns true if the message should be printed at the given timestamp, otherwise returns false.

Constraints:

• Messages are processed in non-decreasing order of timestamps.
• Each message is a non-empty string.
• There can be multiple messages with the same content at different timestamps.

Thought Process

To solve this problem, we need to track the last time each unique message was printed. When a new message arrives, we check whether at least 10 seconds have passed since it was last printed. If so, we allow it to be printed and update the record; otherwise, we block it.

The naive (brute-force) approach would be to keep a complete log of all messages and their timestamps, and for each new message, scan back through the log to see if that message was printed in the last 10 seconds. However, this is inefficient, especially if there are many messages.

To optimize, we realize that we only need to remember the most recent timestamp for each unique message. This allows us to use a hash map (dictionary) where the key is the message and the value is the last printed timestamp. Checking and updating this map is very fast (constant time).

Solution Approach

We will use a hash map (dictionary) to store each message and the last timestamp it was printed. Here’s how the algorithm works step by step:

1. Initialization: Create an empty hash map to store the last printed timestamp for each message.
2. Processing a message: When shouldPrintMessage(timestamp, message) is called:
   • If the message is not in the map, it means it has never been printed, so we can print it. Add it to the map with the current timestamp.
   • If the message is in the map, check the difference between the current timestamp and the stored timestamp. If the difference is at least 10, update the map with the new timestamp and print the message.
   • If the difference is less than 10, do not print the message.
3. Efficiency: Using a hash map allows us to check and update the last print time for any message in O(1) time.

This approach is both simple and efficient, making it suitable for real-time processing of large message streams.

Example Walkthrough

Let's walk through an example to see how the logger works:

• logger.shouldPrintMessage(1, "foo") → true (first time, so print and record timestamp 1)
• logger.shouldPrintMessage(2, "bar") → true (first time, so print and record timestamp 2)
• logger.shouldPrintMessage(3, "foo") → false ("foo" was printed at 1, only 2 seconds ago)
• logger.shouldPrintMessage(8, "bar") → false ("bar" was printed at 2, only 6 seconds ago)
• logger.shouldPrintMessage(10, "foo") → false ("foo" was printed at 1, only 9 seconds ago)
• logger.shouldPrintMessage(11, "foo") → true ("foo" was last printed at 1, now 10 seconds have passed, so print and update timestamp to 11)

At each step, the logger checks the last timestamp for the message and decides whether enough time has passed to allow printing.

Code Implementation

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

    def shouldPrintMessage(self, timestamp: int, message: str) -> bool:
        if message not in self.msg_timestamp or timestamp - self.msg_timestamp[message] >= 10:
            self.msg_timestamp[message] = timestamp
            return True
        return False
      

class Logger {
public:
    Logger() {}

    bool shouldPrintMessage(int timestamp, string message) {
        if (msg_timestamp.find(message) == msg_timestamp.end() || 
            timestamp - msg_timestamp[message] >= 10) {
            msg_timestamp[message] = timestamp;
            return true;
        }
        return false;
    }
private:
    unordered_map<string, int> msg_timestamp;
};
      

import java.util.*;

public class Logger {
    private Map<String, Integer> msgTimestamp;

    public Logger() {
        msgTimestamp = new HashMap<>();
    }

    public boolean shouldPrintMessage(int timestamp, String message) {
        if (!msgTimestamp.containsKey(message) || timestamp - msgTimestamp.get(message) >= 10) {
            msgTimestamp.put(message, timestamp);
            return true;
        }
        return false;
    }
}
      

class Logger {
    constructor() {
        this.msgTimestamp = new Map();
    }

    shouldPrintMessage(timestamp, message) {
        if (!this.msgTimestamp.has(message) || timestamp - this.msgTimestamp.get(message) >= 10) {
            this.msgTimestamp.set(message, timestamp);
            return true;
        }
        return false;
    }
}
      

Time and Space Complexity

• Brute-force Approach:
  • Time Complexity: O(N) per query, where N is the number of logged messages, because we would need to scan the entire log for each message.
  • Space Complexity: O(N), since we store every message and timestamp.
• Optimized Approach (Hash Map):
  • Time Complexity: O(1) per query, as hash map lookups and updates are constant time on average.
  • Space Complexity: O(M), where M is the number of unique messages seen.

The optimized solution is much more efficient, especially when processing a large number of messages.

Summary

The Logger Rate Limiter problem is elegantly solved by using a hash map to keep track of the last printed timestamp for each unique message. This allows us to make print decisions in constant time, ensuring efficiency even with a high volume of messages. The key insight is recognizing that we only need to remember the last timestamp for each message, not the entire log. This approach is simple, fast, and highly scalable.