Skip to main content
CodePeet

CodePeet 700 Complete DSA Sheet

Logger Rate Limiter

Try it yourself
EasyProblemExternal link

Description

A logger receives a stream of messages, each with the time it arrives, in seconds. It prints a message only if that message hasn't printed in the last 10 seconds: a message printed at time t can't print again until t + 10. Messages arrive in time order, and several can arrive in the same second.

Implement the Logger class:

  • Logger() starts a logger that has printed nothing.
  • bool shouldPrintMessage(int timestamp, string message) returns true if message prints at timestamp, and false otherwise.

Examples

Example 1

Input:

["Logger", "shouldPrintMessage", "shouldPrintMessage", "shouldPrintMessage", "shouldPrintMessage", "shouldPrintMessage", "shouldPrintMessage"]
[[], [1, "foo"], [2, "bar"], [3, "foo"], [8, "bar"], [10, "foo"], [11, "foo"]]

Output: [null, true, true, false, false, false, true]

Explanation: foo prints at 1, so it's refused until 11: at 3 and at 10 it's too soon, and at 11 it prints again. bar prints at 2 and is refused at 8.

Example 2

Input:

["Logger", "shouldPrintMessage", "shouldPrintMessage", "shouldPrintMessage", "shouldPrintMessage"]
[[], [5, "ping"], [5, "ping"], [14, "ping"], [15, "ping"]]

Output: [null, true, false, false, true]

Explanation: The same second twice: only the first prints. 14 is still inside the 10 seconds after 5; at 15 the block is over.

Example 3

Input:

["Logger", "shouldPrintMessage", "shouldPrintMessage", "shouldPrintMessage", "shouldPrintMessage"]
[[], [0, "a"], [0, "b"], [9, "a"], [10, "b"]]

Output: [null, true, true, false, true]

Explanation: Each message has its own clock: a and b both print at 0, a is refused at 9 and b prints at 10.

Constraints

  • 0 ≤ timestamp ≤ 10⁹
  • Every timestamp is passed in non-decreasing order
  • 1 ≤ message.length ≤ 30
  • At most 10⁴ calls are made to shouldPrintMessage

Editorial

Brute Force

Intuition

Keep every print: its time and its message. When a message arrives, look through the prints for the same message printed less than 10 seconds ago. If there's one, refuse it; if not, print it and add it to the list.

Step-by-Step Explanation

Let's trace Example 1:

  1. shouldPrintMessage(1, "foo"): nothing has printed yet, so it prints and goes on the end of the list. That call looked at 0 prints.
  2. shouldPrintMessage(2, "bar"): no print of "bar" is in the list, so it prints and goes on the end of the list. That call looked at 1 print.
  3. shouldPrintMessage(3, "foo"): "foo" printed at 1, 2 seconds ago, so it's refused. That call looked at 1 print.
  4. shouldPrintMessage(8, "bar"): "bar" printed at 2, 6 seconds ago, so it's refused. That call looked at 2 prints.
  5. shouldPrintMessage(10, "foo"): "foo" printed at 1, 9 seconds ago, so it's refused. That call looked at 1 print.
  6. shouldPrintMessage(11, "foo"): its last print, at 1, is 10 seconds old, so it prints and goes on the end of the list. That call looked at 2 prints.

Every Print in a List — Each call reads the prints from the oldest, looking for its own message less than 10 seconds old.

Algorithm

  1. Keep a list of every print, as (time, message).
  2. For a call at timestamp, read the list for a print of the same message with timestamp - time < 10.
  3. If there is one, return false. Otherwise add (timestamp, message) to the list and return true.

Code

class Logger {
    vector<pair<int, string>> printed;        // every print, as (time, message), oldest first
public:
    Logger() {
    }

    bool shouldPrintMessage(int timestamp, string message) {
        for (auto& [t, m] : printed)
            if (m == message && timestamp - t < 10) return false;   // printed less than 10 seconds ago
        printed.push_back({timestamp, message});
        return true;
    }
};

class Logger:
    def __init__(self):
        self.printed = []                     # every print, as (time, message), oldest first

    def shouldPrintMessage(self, timestamp: int, message: str) -> bool:
        for t, m in self.printed:
            if m == message and timestamp - t < 10:
                return False                  # printed less than 10 seconds ago
        self.printed.append((timestamp, message))
        return True

class Logger {
    private final List<Integer> times = new ArrayList<>();       // every print, oldest first: its time
    private final List<String> messages = new ArrayList<>();     // and its message

    public Logger() {
    }

    public boolean shouldPrintMessage(int timestamp, String message) {
        for (int i = 0; i < times.size(); i++)
            if (messages.get(i).equals(message) && timestamp - times.get(i) < 10) return false;
        times.add(timestamp);
        messages.add(message);
        return true;
    }
}

var Logger = function() {
    this.printed = [];                        // every print, as [time, message], oldest first
};

Logger.prototype.shouldPrintMessage = function(timestamp, message) {
    for (const [t, m] of this.printed)
        if (m === message && timestamp - t < 10) return false;   // printed less than 10 seconds ago
    this.printed.push([timestamp, message]);
    return true;
};

Complexity Analysis

Time Complexity: O(p) per call

A call reads every print so far, p of them; n calls take O(n²) in the worst case.

Space Complexity: O(p)

The list keeps every print for good.

Why This Approach Is Not Efficient

Every call reads the whole list, and the list only grows. On a test of 10⁴ calls, each a different message, that's about 5 × 10⁷ comparisons: on the judge the list took 2.29 s in Python, the map below 73 ms. And most of what the list holds can't matter. Only a message's last print can block it, and all that print says is when the block ends.

Optimal Approach - The Time It May Print Again

Intuition

Keep, for each message, only the first time it may print again. A message arriving at timestamp prints if timestamp has reached that time, or if the message is new; then its time becomes timestamp + 10. A refused message changes nothing, since only a print starts a new 10 seconds. Each call reads and writes one entry of a hash map.

Step-by-Step Explanation

Let's trace Example 1 again:

  1. shouldPrintMessage(1, "foo"): "foo" isn't in the map, so it prints, and the map keeps 11 for it, the first time it may print again.
  2. shouldPrintMessage(2, "bar"): "bar" isn't in the map, so it prints, and the map keeps 12 for it, the first time it may print again.
  3. shouldPrintMessage(3, "foo"): 3 is before 11, so it's refused, and the map stays as it is.
  4. shouldPrintMessage(8, "bar"): 8 is before 12, so it's refused, and the map stays as it is.
  5. shouldPrintMessage(10, "foo"): 10 is before 11, so it's refused, and the map stays as it is.
  6. shouldPrintMessage(11, "foo"): 11 has reached 11, so it prints, and its time moves on to 21.

The Time It May Print Again — Each call looks up its own message: before that time it's refused, from then on it prints and moves the time on.

Algorithm

  1. Keep a hash map from each message to the first time it may print again.
  2. For a call, if message is in the map and timestamp is before its time, return false.
  3. Otherwise set its time to timestamp + 10 and return true.

Code

class Logger {
    unordered_map<string, int> nextTime;      // message -> the first time it may print again
public:
    Logger() {
    }

    bool shouldPrintMessage(int timestamp, string message) {
        auto it = nextTime.find(message);
        if (it != nextTime.end() && timestamp < it->second) return false;
        nextTime[message] = timestamp + 10;
        return true;
    }
};

class Logger:
    def __init__(self):
        self.next_time = {}                   # message -> the first time it may print again

    def shouldPrintMessage(self, timestamp: int, message: str) -> bool:
        if timestamp < self.next_time.get(message, 0):
            return False
        self.next_time[message] = timestamp + 10
        return True

class Logger {
    private final Map<String, Integer> nextTime = new HashMap<>();   // message -> the first time it may print again

    public Logger() {
    }

    public boolean shouldPrintMessage(int timestamp, String message) {
        if (timestamp < nextTime.getOrDefault(message, 0)) return false;
        nextTime.put(message, timestamp + 10);
        return true;
    }
}

var Logger = function() {
    this.nextTime = new Map();                // message -> the first time it may print again
};

Logger.prototype.shouldPrintMessage = function(timestamp, message) {
    if (timestamp < (this.nextTime.get(message) ?? 0)) return false;
    this.nextTime.set(message, timestamp + 10);
    return true;
};

Complexity Analysis

Time Complexity: O(1) per call

One lookup and at most one write in a hash map, on average.

Space Complexity: O(m)

One entry per different message, m of them. The map never forgets a message; when memory matters, a queue of the last 10 seconds' prints lets the logger drop each message once it's 10 seconds old.

Common Mistakes

Each of these looks right on a quick read, and the tests still reject it. The outputs below come from running the code.

Blocking the 10th second too. if message in self.last and timestamp - self.last[message] <= 10:

On Example 1 it returns [null, true, true, false, false, false, false]; the answer is [null, true, true, false, false, false, true]. A message printed at t is held back for the 10 seconds t to t + 9, and prints again at t + 10. Comparing with <= refuses it at t + 10 as well, a second too long.

Restarting the clock on a refused message. self.last[message] = timestamp

On Example 2 it returns [null, true, false, false, false]; the answer is [null, true, false, false, true]. Only a message that prints starts its 10 seconds. Saving the time on every call, printed or not, lets a message that keeps arriving every few seconds block itself for ever.

One clock for every message. if self.last is not None and timestamp - self.last < 10:

On Example 3 it returns [null, true, false, false, true]; the answer is [null, true, true, false, true]. The limit is per message: foo printing says nothing about bar. One shared time refuses every other message for 10 seconds after any print.

Where This Pattern Is Taught

This problem practises keeping only the history a question needs: for each message, the time it may print again. It's taught in Designing with History.