Logger Rate Limiter
Easy · Design · Design · Hash Table · Data Stream
Problem
Build the rate limiter that sits in front of a noisy log. Messages reach the logger one call at a time, each with the second it arrived:
- shouldPrintMessage(timestamp, message) returns True if this message should be written to the log now, and False if it should be dropped.
A given message text may be printed at most once in any 10 seconds. Once it prints at time t, identical text is dropped for every call before t + 10 and allowed again from t + 10 on. Only an actual print starts that 10-second quiet period; a dropped call changes nothing. Different texts are independent, and matching is exact (case and spaces count).
Calls arrive in time order (timestamps never decrease), and several may share a second.
Your tests replay a call sequence: the first entry names the class, each later entry is a method with its arguments, and the constructor reports None.
Examples
Input: shouldPrintMessage(1,"foo"), (2,"bar"), (3,"foo"), (8,"bar"), (10,"foo"), (11,"foo") Output: true, true, false, false, false, true
"foo" prints at 1, so it is quiet until 11: the calls at 3 and 10 are dropped and the one at 11 prints. "bar" prints at 2 and is still quiet at 8.
Input: shouldPrintMessage(0,"x"), (6,"x"), (9,"x"), (10,"x") Output: true, false, false, true
The drops at 6 and 9 do not push the quiet period back; it still ends at 0 + 10.
Constraints
- 0 <= timestamp <= 10^9
- Timestamps never decrease from one call to the next
- 1 <= message.length <= 30
- At most 10^4 calls to shouldPrintMessage
Approaches
- Queue and set of recent prints, evicting the expired — time amortized O(1) per call, space O(messages printed in the last 10 s)
Follow-up
The map grows with every distinct message and never shrinks. On a server that logs for months, how do you bound memory, and what changes if several threads call the logger at once?
Related problems
Start free on Cariara · Coding problems · System design studio
