Logger Rate Limiter
Logger Rate Limiter is a easy design data structures problem solved with the hash map + array pattern.
The best approach, optimal (queue of recent prints + set), runs in O(1) amortized per call time and O(w) space.
Below are 3 approaches in Java, Python, C++ and JavaScript, from brute force (scan every printed message) up.
Problem
Build a Logger that receives a stream of log messages, each with a timestamp in seconds, and decides whether each one should actually be printed. The rule: a message may be printed only if the same message was not printed during the previous 10 seconds. Once a message is printed at time t, every copy of it arriving before time t + 10 is suppressed.
Implement Logger(), which starts with nothing printed, and shouldPrintMessage(timestamp, message), which returns true if the message is printed now and false if it is suppressed. A suppressed message does not count as printed.
Calls arrive in non-decreasing order of timestamp, and several calls may share the same timestamp.
Examples
Example 1
- Input
Logger(), shouldPrintMessage(1, "boot"), shouldPrintMessage(3, "disk"), shouldPrintMessage(5, "boot"), shouldPrintMessage(11, "boot"), shouldPrintMessage(12, "disk"), shouldPrintMessage(13, "disk")- Output
true, true, false, true, false, true- Why
- "boot" printed at 1 is blocked until 11, so 5 is refused and 11 is allowed; "disk" printed at 3 is blocked until 13, so 12 is refused and 13 is allowed.
Example 2
- Input
Logger(), shouldPrintMessage(7, "a"), shouldPrintMessage(7, "a"), shouldPrintMessage(16, "a"), shouldPrintMessage(17, "a"), shouldPrintMessage(27, "a")- Output
true, false, false, true, true- Why
- A refused call does not restart the 10-second wait: after printing at 7 the next print is allowed at 17, and after that at 27.
Constraints
0 <= timestamp <= 10^9- Calls arrive in chronological order: each
timestampis greater than or equal to the previous one. 1 <= message.length <= 30, lowercase English letters.- At most
10^4calls toshouldPrintMessage.
Solve it here
Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.
Your own testcases: Run checks these, and the expected output comes from our reference solution.
My submissions
Nothing yet. Every Run and Submit you make while signed in shows up here.
| When | Result | Tests | Runtime | Your time | Type |
|---|
Run checks the testcases above (2 examples, or your own). Submit also runs 10 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.
Solutions
Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.
| Approach | Time | Space |
|---|---|---|
| Brute force (scan every printed message) | O(n) per call | O(n) |
| Hash map of next allowed time | O(1) per call | O(m) |
| Optimal (queue of recent prints + set) | O(1) amortized per call | O(w) |
1Brute force (scan every printed message)
O(n) per callEach call scans every message printed so far.O(n)Every printed message is stored forever.Keep a list of every message that was actually printed, with its time. For a new call, scan the whole list for the same message printed less than 10 seconds ago.
- Keep two parallel lists: print times and printed messages.
- For a call (t, m), scan all entries; if one has message m and time > t - 10, return false.
- Otherwise append (t, m) and return true.
class Logger {
private final List<Integer> times = new ArrayList<>();
private final List<String> messages = new ArrayList<>();
public Logger() {
}
public boolean shouldPrintMessage(int timestamp, String message) {
for (int i = 0; i < times.size(); i++) {
if (messages.get(i).equals(message) && times.get(i) > timestamp - 10) {
return false;
}
}
times.add(timestamp);
messages.add(message);
return true;
}
}class Logger:
def __init__(self):
self.times: List[int] = []
self.messages: List[str] = []
def shouldPrintMessage(self, timestamp: int, message: str) -> bool:
for i in range(len(self.times)):
if self.messages[i] == message and self.times[i] > timestamp - 10:
return False
self.times.append(timestamp)
self.messages.append(message)
return Trueclass Logger {
vector<int> times;
vector<string> messages;
public:
Logger() {}
bool shouldPrintMessage(int timestamp, string message) {
for (int i = 0; i < (int)times.size(); i++) {
if (messages[i] == message && times[i] > timestamp - 10) {
return false;
}
}
times.push_back(timestamp);
messages.push_back(message);
return true;
}
};class Logger {
constructor() {
this.times = [];
this.messages = [];
}
shouldPrintMessage(timestamp, message) {
for (let i = 0; i < this.times.length; i++) {
if (this.messages[i] === message && this.times[i] > timestamp - 10) {
return false;
}
}
this.times.push(timestamp);
this.messages.push(message);
return true;
}
}2Hash map of next allowed time
O(1) per callOne hash lookup and at most one insert per call (on average).O(m)One entry per distinct message ever printed, m of them, even ones that are long expired.Store, for each message, the earliest second at which it may be printed again. A call is allowed when the current time has reached that second; only then is the deadline moved to timestamp + 10.
- Look up message in the map (missing means it was never printed).
- If it is present and timestamp < stored time, return false.
- Otherwise store timestamp + 10 for the message and return true.
class Logger {
private final Map<String, Integer> nextAllowed = new HashMap<>();
public Logger() {
}
public boolean shouldPrintMessage(int timestamp, String message) {
Integer next = nextAllowed.get(message);
if (next != null && timestamp < next) {
return false;
}
nextAllowed.put(message, timestamp + 10);
return true;
}
}class Logger:
def __init__(self):
self.next_allowed: Dict[str, int] = {}
def shouldPrintMessage(self, timestamp: int, message: str) -> bool:
nxt = self.next_allowed.get(message)
if nxt is not None and timestamp < nxt:
return False
self.next_allowed[message] = timestamp + 10
return Trueclass Logger {
unordered_map<string, int> nextAllowed;
public:
Logger() {}
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;
}
};class Logger {
constructor() {
this.nextAllowed = new Map();
}
shouldPrintMessage(timestamp, message) {
const next = this.nextAllowed.get(message);
if (next !== undefined && timestamp < next) {
return false;
}
this.nextAllowed.set(message, timestamp + 10);
return true;
}
}3Optimal (queue of recent prints + set)
O(1) amortized per callEvery printed message is pushed once and popped at most once; the set operations are O(1) on average.O(w)Only prints from the last 10 seconds are kept: w is the number of distinct messages printed in any 10-second window.Only prints from the last 10 seconds can block anything. Keep those prints in a queue in time order plus a set of their messages. Before answering, pop prints that are 10 or more seconds old from the front and remove them from the set; the message is allowed exactly when it is not in the set. Same O(1) amortized time as the map, but memory stays bounded by the messages printed in the last 10 seconds.
- While the queue's front was printed at time <= timestamp - 10, pop it and remove its message from the set.
- If message is in the set, return false.
- Otherwise push (timestamp, message), add message to the set, and return true.
class Logger {
private final Deque<Integer> times = new ArrayDeque<>();
private final Deque<String> messages = new ArrayDeque<>();
private final Set<String> recent = new HashSet<>();
public Logger() {
}
public boolean shouldPrintMessage(int timestamp, String message) {
while (!times.isEmpty() && times.peekFirst() <= timestamp - 10) {
times.pollFirst();
recent.remove(messages.pollFirst());
}
if (recent.contains(message)) {
return false;
}
times.addLast(timestamp);
messages.addLast(message);
recent.add(message);
return true;
}
}from collections import deque
class Logger:
def __init__(self):
self.queue = deque() # (time, message), oldest first
self.recent: Set[str] = set()
def shouldPrintMessage(self, timestamp: int, message: str) -> bool:
while self.queue and self.queue[0][0] <= timestamp - 10:
_, old = self.queue.popleft()
self.recent.discard(old)
if message in self.recent:
return False
self.queue.append((timestamp, message))
self.recent.add(message)
return Trueclass Logger {
deque<pair<int, string>> q; // (time, message), oldest first
unordered_set<string> recent;
public:
Logger() {}
bool shouldPrintMessage(int timestamp, string message) {
while (!q.empty() && q.front().first <= timestamp - 10) {
recent.erase(q.front().second);
q.pop_front();
}
if (recent.count(message)) {
return false;
}
q.push_back({timestamp, message});
recent.insert(message);
return true;
}
};class Logger {
constructor() {
this.times = [];
this.messages = [];
this.head = 0; // index of the oldest kept print
this.recent = new Set();
}
shouldPrintMessage(timestamp, message) {
while (this.head < this.times.length && this.times[this.head] <= timestamp - 10) {
this.recent.delete(this.messages[this.head]);
this.head++;
}
if (this.head > 1024 && this.head * 2 > this.times.length) {
// drop the popped prefix so memory stays bounded
this.times = this.times.slice(this.head);
this.messages = this.messages.slice(this.head);
this.head = 0;
}
if (this.recent.has(message)) {
return false;
}
this.times.push(timestamp);
this.messages.push(message);
this.recent.add(message);
return true;
}
}Edge cases to test
- The same message twice at the same second: only the first is printed
- A repeat exactly 10 seconds later is allowed; 9 seconds later is not
- A refused message must not push its own deadline further
- Different messages never block each other
Hints
Hint 1
For each message you only need one fact: the earliest time it may be printed again.
Hint 2
A hash map from message to that time answers every call in O(1).
Hint 3
To keep memory small, notice that a message printed more than 10 seconds ago can be forgotten entirely. Since timestamps only grow, a queue of recent prints lets you drop old ones from the front.
FAQ
What is the best time complexity for Logger Rate Limiter?
Optimal (queue of recent prints + set) runs in O(1) amortized per call time and O(w) extra space. Every printed message is pushed once and popped at most once; the set operations are O(1) on average.
Which pattern does Logger Rate Limiter use?
It is a design data structures problem that uses the hash map + array pattern. Other problems with the same pattern: Insert Delete GetRandom O(1), Insert Delete GetRandom O(1) - Duplicates allowed, Design Parking System.
Is there a brute force solution for Logger Rate Limiter?
Yes. Brute force (scan every printed message) takes O(n) per call time and O(n) space. Keep a list of every message that was actually printed, with its time.
Which edge cases should I test for Logger Rate Limiter?
The same message twice at the same second: only the first is printed; A repeat exactly 10 seconds later is allowed; 9 seconds later is not; A refused message must not push its own deadline further; Different messages never block each other.