Krammer's blog

https://leetcode.com/problems/logger-rate-limiter/ from Google

Solutions:

1. Hash map to store the time

Use a hash map to store the incoming messages and timestamp. Use the message as the key, and the timestamp is the value. Whenever we find an existing key, we check that if the time gap is more than 10 second. If yes, replace the timestamp. If no, we return false so that we don’t print the message.

 1class Logger {
 2public:
 3    unordered_map<string, int> m;
 4    /** Initialize your data structure here. */
 5    Logger() {
 6        
 7    }
 8    
 9    /** Returns true if the message should be printed in the given timestamp, otherwise returns false.
10        If this method returns false, the message will not be printed.
11        The timestamp is in seconds granularity. */
12    bool shouldPrintMessage(int timestamp, string message) {
13        if (m.count(message)) {
14            if (timestamp - m[message] >= 10) {
15                m[message] = timestamp;
16                return true;
17            }
18        } else {
19            m[message] = timestamp;
20            return true;
21        }
22        
23        return false;
24    }
25};
26
27/**
28 * Your Logger object will be instantiated and called as such:
29 * Logger* obj = new Logger();
30 * bool param_1 = obj->shouldPrintMessage(timestamp,message);
31 */

Time complexity: O(1). Space complexity: O(M), where M is the size of all incoming messages. Over the time, the hash map would have an entry for each unique message. As a result, we might consider a clean up process to release the stale entries in the hash map.

LeetCode 359 Logger Rate Limiter

1. Hash map to store the time