Design Logger Rate Limiter
Asked at Atlassian, Netflix
Problem
Design a logger system that receives a message and prints it if it was not printed within the last 10 seconds. Each unique message should only be printed at most once in a 10-second window. This tests your ability to design a time-based throttle using a hash map.
Asked At
| Company | Difficulty | |
|---|---|---|
| Atlassian | Easy | View all Atlassian questions → |
| Netflix | Easy | View all Netflix questions → |
How to Think About It
The simplest approach: a hash map where key = message, value = timestamp of last print. When a new message arrives, check if it's been >= 10 seconds since the last print. If yes, print and update. If no, discard.
Why a hash map works: you need O(1) lookup for "was this message printed recently?" The map stores exactly one timestamp per message. Old entries are naturally handled by the timestamp check.
Memory concern: over time, the map grows unbounded. In production, you'd periodically evict entries older than 10 seconds. For an interview, mention this as a follow-up optimization.
Visual walkthrough:
Logger logger = new Logger();
logger.shouldPrintMessage(1, "foo") -> true (map: {"foo":1})
logger.shouldPrintMessage(2, "bar") -> true (map: {"foo":1, "bar":2})
logger.shouldPrintMessage(3, "foo") -> false (foo printed at 1, 3-1=2 < 10)
logger.shouldPrintMessage(11, "foo") -> true (11-1=10 >= 10, update {"foo":11})
logger.shouldPrintMessage(12, "bar") -> false (bar printed at 2, 12-2=10 >= 10? Yes! Return true.)
Edge cases: same message twice at same timestamp (return false), timestamp can be non-increasing (always check against last stored timestamp, not current time).
Optimal Approach
Use a hash map mapping message -> last_printed_timestamp.
For each call to shouldPrintMessage(timestamp, message):
- If message not in map: print (return true), store timestamp.
- If message in map: check if
timestamp - stored_timestamp >= 10. If yes, print and update. If no, don't print.
The hash map gives O(1) per call. Space is O(n) where n = number of unique messages.
Time: O(1) per call. Space: O(n).
What Trips People Up in Real Interviews
Forgetting that the 10-second window is relative to the last printed time, not absolute. Message printed at t=5 can be reprinted at t=15, not t=12 (5+10=15).
Using current time instead of the provided timestamp. The function receives a timestamp parameter -- use it, not time.time(). The caller controls the clock.
Storing a list of timestamps per message instead of just the last one. You only need the most recent timestamp. Old timestamps are always expired.
Not handling the case where the message was never printed before. If the message is new, print it immediately regardless of timestamp.
Comparing with >= instead of >. The problem says "within the last 10 seconds." At exactly 10 seconds, the message should be printable. Use >= (not >).
Solution Code
class Logger:
def __init__(self):
self.msg_time = {}
def shouldPrintMessage(self, timestamp, message):
if message not in self.msg_time or timestamp - self.msg_time[message] >= 10:
self.msg_time[message] = timestamp
return True
return FalseFrequently Asked Questions
What is the Design Logger Rate Limiter problem?
Design a logger system that receives a message and prints it if it was not printed within the last 10 seconds. Each unique message should only be printed at most once in a 10-second window. This tests your ability to design a time-based throttle using a hash map.
How do you solve Design Logger Rate Limiter?
The optimal approach is described in detail above, including step-by-step walkthroughs, complexity analysis, and solution code in Python. Scroll up to the "Optimal Approach" section.
What companies ask Design Logger Rate Limiter?
Design Logger Rate Limiter is asked at Atlassian, Netflix. It is a easy difficulty problem.
What are common mistakes on Design Logger Rate Limiter?
- Forgetting that the 10-second window is relative to the last printed time, not absolute. Message printed at t=5 can be reprinted at t=15, not t=12 (5+10=15).
- Using current time instead of the provided timestamp. The function receives a timestamp parameter -- use it, not `time.time()`. The caller controls the clock.
- Storing a list of timestamps per message instead of just the last one. You only need the most recent timestamp. Old timestamps are always expired.
- Not handling the case where the message was never printed before. If the message is new, print it immediately regardless of timestamp.
- Comparing with >= instead of >. The problem says "within the last 10 seconds." At exactly 10 seconds, the message should be printable. Use >= (not >).