Logger Rate Limiter
Allow a message at most once every 10 seconds — hash map of last-seen timestamps.
2 min read
hash-map design
Problem#
Design a logger such that shouldPrintMessage(timestamp, message) returns true iff the same message has not been printed within the last 10 seconds.
Examples#
shouldPrintMessage(1, "foo")→true.shouldPrintMessage(2, "bar")→true.shouldPrintMessage(3, "foo")→false.shouldPrintMessage(11, "foo")→true.
Constraints#
- Timestamps are non-decreasing.
Hints#
Hint
Map message -> earliest timestamp it can next be printed.
Approach#
Store nextAllowed[message]. Print iff timestamp >= nextAllowed[message]; if so, set nextAllowed[message] = timestamp + 10. Missing key defaults to 0, which permits the first print.
Solution#
class Logger { unordered_map<string, int> nextAllowed;public: Logger() = default;
bool shouldPrintMessage(int timestamp, string message) { auto it = nextAllowed.find(message); if (it != nextAllowed.end() && timestamp < it->second) return false; nextAllowed[message] = timestamp + 10; return true; }};type Logger struct { nextAllowed map[string]int}
func Constructor() Logger { return Logger{nextAllowed: map[string]int{}}}
func (l *Logger) ShouldPrintMessage(timestamp int, message string) bool { if t, ok := l.nextAllowed[message]; ok && timestamp < t { return false } l.nextAllowed[message] = timestamp + 10 return true}class Logger: def __init__(self): self.next_allowed: dict[str, int] = {}
def shouldPrintMessage(self, timestamp: int, message: str) -> bool: if message in self.next_allowed and timestamp < self.next_allowed[message]: return False self.next_allowed[message] = timestamp + 10 return Trueclass Logger { constructor() { this.nextAllowed = new Map(); } shouldPrintMessage(timestamp, message) { if (this.nextAllowed.has(message) && timestamp < this.nextAllowed.get(message)) { return false; } this.nextAllowed.set(message, timestamp + 10); return true; }}class Logger { private final Map<String, Integer> nextAllowed;
public Logger() { nextAllowed = new HashMap<>(); }
public boolean shouldPrintMessage(int timestamp, String message) { Integer t = nextAllowed.get(message); if (t != null && timestamp < t) return false; nextAllowed.put(message, timestamp + 10); return true; }}class Logger { private nextAllowed: Map<string, number>;
constructor() { this.nextAllowed = new Map(); }
shouldPrintMessage(timestamp: number, message: string): boolean { const t = this.nextAllowed.get(message); if (t !== undefined && timestamp < t) return false; this.nextAllowed.set(message, timestamp + 10); return true; }}Editorial#
Recording “next allowed time” instead of “last printed time” saves an addition on every check — pure preference. Memory grows with the number of distinct messages ever seen; production code would garbage-collect entries older than 10 seconds via a sliding deque, but the spec doesn’t require it.
Complexity#
- Time: O(1) per call.
- Space: O(M) distinct messages.
Concept revision#
Related#