Design a Logger Rate Limiter in C++/Java

  • 时间:2020-10-06 11:32:45
  • 分类:网络文摘
  • 阅读:96 次

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:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
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;
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;

This is the exact same problem that I was asked at the Google phone interview – which I shared on leetcode. And it is nice to have this problem added to the online judge.

The solution is to have a queue that stores the all messages printed in the last 10 seconds (thus we need to de-queue at each function call). We use hash set to store the messages printed in the last 10 second – O(1) for lookup. For messages that are older than 10 second, we don’t need to store them in the hash table, thus removing them when dequeing.

Java’s Pair class is defined in javafx.util.Pair

Your Logger object will be instantiated and called as such:

1
2
  Logger obj = new Logger();
  boolean param_1 = obj.shouldPrintMessage(timestamp,message);
  Logger obj = new Logger();
  boolean param_1 = obj.shouldPrintMessage(timestamp,message);

With the data structures of Set, Queue and Pair, we can implement the rate limit logger in Java:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
import javafx.util.Pair;
 
class Logger {
 
    /** Initialize your data structure here. */
    public Logger() {
        
    }
    
    /** 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) {
        // remove invalid entries
        while (!last10.isEmpty()) {
            Pair<integer , String> key = last10.peek();
            if (timestamp - key.getKey() >= 10) {
                last10.poll();
                cache.remove(key.getValue()); // remove from hash set
            } else {
                break;
            }
        }   
        if (cache.contains(message)) {
            return false; //  printed in last 10 seconds
        }
        // inserting the entry
        cache.add(message);
        last10.add(new Pair(timestamp, message));
        return true;        
    }
    
    private Set<string> cache = new HashSet<>();
    private Queue<pair <Integer, String>> last10 = new LinkedList<>();
}
import javafx.util.Pair;

class Logger {

    /** Initialize your data structure here. */
    public Logger() {
        
    }
    
    /** 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) {
        // remove invalid entries
        while (!last10.isEmpty()) {
            Pair<integer , String> key = last10.peek();
            if (timestamp - key.getKey() >= 10) {
                last10.poll();
                cache.remove(key.getValue()); // remove from hash set
            } else {
                break;
            }
        }   
        if (cache.contains(message)) {
            return false; //  printed in last 10 seconds
        }
        // inserting the entry
        cache.add(message);
        last10.add(new Pair(timestamp, message));
        return true;        
    }
    
    private Set<string> cache = new HashSet<>();
    private Queue<pair <Integer, String>> last10 = new LinkedList<>();
}

The C++ implementation is similar, as follows:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class Logger {
public:
    /** Initialize your data structure here. */
    Logger() {
            
    }
    
    /** 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. */
    bool shouldPrintMessage(int timestamp, string message) {
        // remove invalid entries
        while (!last10.empty()) {
            auto key = last10.front();
            if (timestamp - key.first >= 10) {
                last10.pop();
                cache.erase(key.second); // remove from hash set
            } else {
                break;
            }
        }   
        if (cache.count(message)) {
            return false; //  printed in last 10 seconds
        }
        // inserting the entry
        cache.insert(message);
        last10.push(make_pair(timestamp, message));
        return true;
    }
    
private:
    unordered_set<string> cache;
    queue<pair <int, string>> last10;
};
class Logger {
public:
    /** Initialize your data structure here. */
    Logger() {
            
    }
    
    /** 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. */
    bool shouldPrintMessage(int timestamp, string message) {
        // remove invalid entries
        while (!last10.empty()) {
            auto key = last10.front();
            if (timestamp - key.first >= 10) {
                last10.pop();
                cache.erase(key.second); // remove from hash set
            } else {
                break;
            }
        }   
        if (cache.count(message)) {
            return false; //  printed in last 10 seconds
        }
        // inserting the entry
        cache.insert(message);
        last10.push(make_pair(timestamp, message));
        return true;
    }
    
private:
    unordered_set<string> cache;
    queue<pair <int, string>> last10;
};

When messages can be printed, we need to enqueue and add them to the hash set. Thus the memory usage can be controlled i.e entries are cleared (dequeued and erased from the set).

–EOF (The Ultimate Computing & Technology Blog) —

推荐阅读:
饮食健康与胃病食疗(二):慢性胃炎的饮食调理  饮食健康与胃病食疗(三):这样饮食降低胃癌风险  冬至时节,常吃这几种传统美食可补阳、防寒!  只有这样吃大蒜才能杀菌防癌,以前你吃对了吗  丝瓜营养丰富,其对人体的保健功效如此之多  患有胃病的人常吃这些食物,可以帮助调理好胃  山药营养丰富食疗价值高,助爱美女性吃出好身材  糖尿病患者常有这些饮食误区,朋友们注意啦!  网络上流传甚广的垃圾食品方便面有毒、致癌的传闻是真的吗?  经常吃核桃仁可以补脑是真的吗 一天吃多少核桃才健康 
评论列表
添加评论