Logger Rate Limiter
Problem
Design a logger that, given a timestamp and a message, returns true iff the message hasn't been printed in the last 10 seconds.
shouldPrintMessage(1,"foo"), (2,"bar"), (3,"foo"), (8,"bar"), (11,"foo")[true, true, false, false, true]class Logger:
def __init__(self):
self.gate = {}
def shouldPrintMessage(self, t, msg):
if msg in self.gate and t < self.gate[msg]:
return False
self.gate[msg] = t + 10
return Trueclass Logger {
constructor() { this.gate = new Map(); }
shouldPrintMessage(t, msg) {
if (this.gate.has(msg) && t < this.gate.get(msg)) return false;
this.gate.set(msg, t + 10);
return true;
}
}class Logger {
Map gate = new HashMap<>();
public boolean shouldPrintMessage(int t, String msg) {
if (gate.containsKey(msg) && t < gate.get(msg)) return false;
gate.put(msg, t + 10); return true;
}
} class Logger {
unordered_map gate;
public:
bool shouldPrintMessage(int t, string msg) {
if (gate.count(msg) && t < gate[msg]) return false;
gate[msg] = t + 10; return true;
}
}; Explanation
The clever part of this problem is realizing you do not need to store a history of past prints. You only ever need one number per message: the earliest time it is allowed to be printed again.
We keep a hash map called gate that maps each message to that "next allowed" timestamp. When a message comes in at time t, we check the gate. If the message is in the map and t is still before its stored time, it is too soon, so we return false and print nothing.
Otherwise we are clear to print. We record gate[msg] = t + 10 so that this message is blocked until 10 seconds have passed, and return true.
Example: ("foo", 1) prints and sets gate["foo"] = 11. Then ("foo", 3) sees 3 < 11, so it is blocked. Later ("foo", 11) sees 11 is not less than 11, so it prints again and resets the gate to 21.
Each call is just one map lookup and maybe one write, so it is O(1) time, and we store one entry per distinct message.