Design a Logger Rate Limiter in C++/Java

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) —