{x}
blog image

Logger Rate Limiter

Solution Explanation

This problem requires designing a logger that limits the rate at which identical messages are printed. A message can only be printed if at least 10 seconds have passed since the last time the same message was printed.

The optimal solution uses a hash map (dictionary in Python) to store the last print time for each unique message. This allows for O(1) lookup and update of the last print time.

Approach

  1. Data Structure: We use a hash map (or dictionary) to store the last print timestamp for each message. The key is the message string, and the value is the timestamp of the last time that message was printed.

  2. shouldPrintMessage Function:

    • Look up the message in the hash map. If it's not found, it means it's the first time seeing this message, so we print it.
    • If the message is found, compare its last print time (last_print_time) with the current timestamp.
    • If current_timestamp >= last_print_time + 10, it means 10 seconds or more have passed, so we print it and update last_print_time.
    • Otherwise, we don't print it.

Code Explanation (Python)

class Logger:
    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.limiter = {} #Hashmap to store last print time for each message
 
    def shouldPrintMessage(self, timestamp: int, message: str) -> bool:
        """
        Returns true if the message should be printed in the given timestamp, otherwise returns false.
        If this method returns false, the message will not be printed.
        The timestamp is in seconds granularity.
        """
        last_print_time = self.limiter.get(message, 0) #Get last print time, default to 0 if not found.
        if timestamp >= last_print_time + 10: #Check if 10 seconds have passed
            self.limiter[message] = timestamp + 10 #Update last print time
            return True
        else:
            return False

Code Explanation (Java)

import java.util.HashMap;
import java.util.Map;
 
class Logger {
    private Map<String, Integer> limiter;
 
    public Logger() {
        limiter = new HashMap<>();
    }
 
    public boolean shouldPrintMessage(int timestamp, String message) {
        int lastPrintTime = limiter.getOrDefault(message, 0);
        if (timestamp >= lastPrintTime + 10) {
            limiter.put(message, timestamp + 10);
            return true;
        } else {
            return false;
        }
    }
}

Code Explanation (Javascript)

/**
 * Initialize your data structure here.
 */
var Logger = function() {
    this.limiter = {};
};
 
/**
 * Returns true if the message should be printed in the given timestamp, otherwise returns false.
        If this method returns false, the message will not be printed.
        The timestamp is in seconds granularity.
 * @param {number} timestamp
 * @param {string} message
 * @return {boolean}
 */
Logger.prototype.shouldPrintMessage = function(timestamp, message) {
    const lastPrintTime = this.limiter[message] || 0;
    if (timestamp >= lastPrintTime + 10) {
        this.limiter[message] = timestamp + 10;
        return true;
    } else {
        return false;
    }
};

Time and Space Complexity

Time Complexity: O(1) for both __init__ and shouldPrintMessage. Hash map lookups and insertions are typically constant time on average.

Space Complexity: O(N), where N is the number of unique messages. The space used is proportional to the number of unique messages stored in the hash map. In the worst case, if all messages are unique, the space complexity will be O(N).