Problem

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.

Examples

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;

Solution

Method 1 – Hash Map for Message Timestamp

Intuition

We need to track the last printed timestamp for each message. By using a hash map to store the last timestamp for each message, we can efficiently check if a message should be printed (i.e., if it hasn’t been printed in the last 10 seconds).

Approach

  1. Use a hash map to store the last printed timestamp for each message.
  2. For each incoming message and timestamp:
    • If the message is not in the map or the difference between the current timestamp and the last printed timestamp is at least 10, print the message and update the timestamp.
    • Otherwise, do not print the message.
  3. Return true if the message should be printed, false otherwise.

Complexity

  • ⏰ Time complexity: O(1) per operation, since hash map lookups and updates are constant time.
  • 🧺 Space complexity: O(m), where m is the number of unique messages.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
class Logger {
    unordered_map<string, int> last;
public:
    Logger() {}
    bool shouldPrintMessage(int timestamp, string message) {
        if (!last.count(message) || timestamp - last[message] >= 10) {
            last[message] = timestamp;
            return true;
        }
        return false;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
class Logger {
    private Map<String, Integer> last;
    public Logger() {
        last = new HashMap<>();
    }
    public boolean shouldPrintMessage(int timestamp, String message) {
        if (!last.containsKey(message) || timestamp - last.get(message) >= 10) {
            last.put(message, timestamp);
            return true;
        }
        return false;
    }
}
1
2
3
4
5
6
7
8
class Logger:
    def __init__(self):
        self.last = {}
    def shouldPrintMessage(self, timestamp: int, message: str) -> bool:
        if message not in self.last or timestamp - self.last[message] >= 10:
            self.last[message] = timestamp
            return True
        return False