Question

Formatted question description: https://leetcode.ca/all/359.html

 359	Logger Rate Limiter

 Design a logger system that receive 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 returns false.

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

 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;

 @tag-design

Algorithm

Use a hash table to create a mapping between the message and the timestamp,

  • If a message is no longer in the hash table, we create a mapping between it and the timestamp and return true.
  • If it is in the hash table, we see if the current timestamp is 10 greater than the timestamp stored in the hash table,
    • If yes, update the hash table and return true
    • Otherwise, return false

Code

Java

  • import java.util.HashMap;
    
    public class Logger_Rate_Limiter {
    
        public class Logger_optimize {
            HashMap<String, Integer> messages; // message => timestamp
    
            /** Initialize your data structure here. */
            public Logger_optimize() {
                this.messages = new HashMap<String, Integer>();
            }
    
            /** 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. */
            public boolean shouldPrintMessage(int timestamp, String message) {
    
                if (timestamp < messages.get(message)) return false;
    
                messages.put(message, timestamp + 10);
    
                return true;
            }
        }
    
    
        public class Logger {
            HashMap<String, Integer> messages; // message => timestamp
    
            /** Initialize your data structure here. */
            public Logger() {
                this.messages = new HashMap<String, Integer>();
            }
    
            /** 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. */
            public boolean shouldPrintMessage(int timestamp, String message) {
                if(messages.containsKey(message)) {
                    if(timestamp - messages.get(message) >= 10) {
                        messages.put(message, timestamp);
    
                        return true;
                    } else {
                        return false;
                    }
                } else {
                    messages.put(message, timestamp);
    
                    return true;
                }
            }
        }
    
    }
    
  • // OJ: https://leetcode.com/problems/logger-rate-limiter/
    // Time: O(1)
    // Space: O(M)
    class Logger {
    private:
        unordered_map<string, int> m;
    public:
        Logger() {}
        bool shouldPrintMessage(int timestamp, string message) {
            bool ans = m.find(message) == m.end() || timestamp - m[message] >= 10;
            if (ans) m[message] = timestamp;
            return ans;
        }
    };
    
  • class Logger(object):
    
      def __init__(self):
        """
        Initialize your data structure here.
        """
        self.d = {}
    
      def shouldPrintMessage(self, timestamp, message):
        """
        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.
        :type timestamp: int
        :type message: str
        :rtype: bool
        """
        if message not in self.d:
          self.d[message] = timestamp
          return True
        elif timestamp - self.d[message] >= 10:
          self.d[message] = timestamp
          return True
        return False
    
    # Your Logger object will be instantiated and called as such:
    # obj = Logger()
    # param_1 = obj.shouldPrintMessage(timestamp,message)
    
    

All Problems

All Solutions