359. Logger Rate Limiter

Problem

The problem is that we have a Logger that is continuously receiving messages, and this message contains two parts, message and timestamp. Then he has a function shouldPrintMessage. When the message is received it will determine if it should be printed based on the message and the timestamp, based on the fact that if the same message is printed within 10 time units it cannot be printed again.

The example of the topic is.

Input
["Logger", "shouldPrintMessage", "shouldPrintMessage", "shouldPrintMessage", "shouldPrintMessage", "shouldPrintMessage", "shouldPrintMessage", " shouldPrintMessage"]
[[], [1, "foo"], [2, "bar"], [3, "foo"], [8, "bar"], [10, "foo"], [11, "foo"]]
Output
[null, true, true, false, false, false, true]

Explanation
Logger logger = new Logger();
logger.shouldPrintMessage(1, "foo"); // return true, next allowed timestamp for "foo" is 1 + 10 = 11
logger.shouldPrintMessage(2, "bar"); // return true, next allowed timestamp for "bar" is 2 + 10 = 12
logger.shouldPrintMessage(3, "foo"); // 3 < 11, return false
logger.shouldPrintMessage(8, "bar"); // 8 < 12, return false
logger.shouldPrintMessage(10, "foo"); // 10 < 11, return false
logger.shouldPrintMessage(11, "foo"); // 11 >= 11, return true, next allowed timestamp for "foo" is 11 + 10 = 21

Parse

This topic is an implementation or design problem. My understanding is that it is really about implementing some functionality with the help of various data structures.

Picking the right data structure is the first step. .

I think map is more suitable here (there are ready-made access functions for easy operation).

The second part is to fully understand the question, consider the usage scenarios and limitations, and implement the function. .

For example, the type of data input (data format), the amount of data input, the time requirement, the space requirement, and so on.

Some small details in this topic, such as whether the output is available at 10 time units, this will make the time judgment more than one equal sign. In addition is the subsequent can not output the message will update the map internal timestamp? This will affect whether the subsequent unprintable content needs to be discarded or stored.

Back to the topic, I think is that I can save the last output time and information, divided into two cases, the first is the message did not appear, then we directly store and return true; the other is the appearance, then we have to take out the last printable time, and then do the time difference judgment, can not be discarded to return false, can be updated and return true.

Write the code.

Code

class Logger {

    Map<String, Integer> log;
    
    public Logger() {
       this.log = new HashMap<>();
    }
    
    public boolean shouldPrintMessage(int timestamp, String message) {
        if (!log.keySet().contains(message)) {
            log.put(message, timestamp);
            return true;
        } 
        int prevTimeStamp = log.get(message);
        if (timestamp - prevTimeStamp >= 10) {
            log.put(message, timestamp);
            return true;
        } else {
            return false;
        }
    }
}

/**} }
 * Your Logger object will be instantiated and called as such:
 * Logger obj = new Logger();
 * boolean param_1 = obj.shouldPrintMessage(timestamp,message);
 */

问题

这个问题是说，我们有一个Logger在持续的接收信息，这个信息包含两部分，message和时间戳。然后他会有一个函数是shouldPrintMessage。当收到信息的时候会根据信息和时间戳判断是否应该打印，依据是同样的信息10个时间单位内如果打印过就不能再次打印。

题目的例子是：

Input
["Logger", "shouldPrintMessage", "shouldPrintMessage", "shouldPrintMessage", "shouldPrintMessage", "shouldPrintMessage", "shouldPrintMessage"]
[[], [1, "foo"], [2, "bar"], [3, "foo"], [8, "bar"], [10, "foo"], [11, "foo"]]
Output
[null, true, true, false, false, false, true]

Explanation
Logger logger = new Logger();
logger.shouldPrintMessage(1, "foo");  // return true, next allowed timestamp for "foo" is 1 + 10 = 11
logger.shouldPrintMessage(2, "bar");  // return true, next allowed timestamp for "bar" is 2 + 10 = 12
logger.shouldPrintMessage(3, "foo");  // 3 < 11, return false
logger.shouldPrintMessage(8, "bar");  // 8 < 12, return false
logger.shouldPrintMessage(10, "foo"); // 10 < 11, return false
logger.shouldPrintMessage(11, "foo"); // 11 >= 11, return true, next allowed timestamp for "foo" is 11 + 10 = 21

解析

这个题目是一个实现题，或者叫设计题。我的理解其实就是借助各种数据结构实现某些功能。

选取合适的数据结构是第一步。

这个题目里要根据信息的message的时间去判断时间间隔，两个值要存储的话要么是一个二元数组，要么可以用Map。这里我觉得map更适合一些（有现成的存取函数，方便操作）。

第二部就是充分理解题意，考虑使用场景和限制，实现功能。

比如数据输入的数据类型（数据格式），输入的数据量，时间上的要求，空间上的要求等等。

这个题目里一些小细节，比如10个时间单位的时候是否可以输出了，这个会让时间判断多一个等号。另外就是后续不能输出的message是否会更新map内部的时间戳？这个会影响到后续不可打印的内容是否需要丢弃或存储。

回到这个题目，我想的就是我存一下上次的可以输出时间以及信息，分两种情况，第一种是信息没出现过，那么我们直接存然后返回true即可；另外就是出现过，那么我们要取出来上次可以打印的时间，然后做时间差判断，不可以就丢弃返回flase，可以就更新并返回true。

代码

class Logger {

    Map<String, Integer> log;
    
    public Logger() {
       this.log = new HashMap<>();
    }
    
    public boolean shouldPrintMessage(int timestamp, String message) {
        if (!log.keySet().contains(message)) {
            log.put(message, timestamp);
            return true;
        } 
        int prevTimeStamp = log.get(message);
        if (timestamp - prevTimeStamp >= 10) {
            log.put(message, timestamp);
            return true;
        } else {
            return false;
        }
    }
}

/**
 * Your Logger object will be instantiated and called as such:
 * Logger obj = new Logger();
 * boolean param_1 = obj.shouldPrintMessage(timestamp,message);
 */