💬 Discord
Sign In
NeetCode #19LC-359EasyArrays & Hashing
← Back to All Problems

#19 · #359 · Logger Rate Limiter(日志速率限制器)

📌 Problem Statement & Constraints

Design a logger that only prints a message if it has not been printed in the last 10 seconds. Implement shouldPrintMessage(timestamp, message). Timestamps are non-decreasing integers (seconds). Constraints: at most 10^4 calls, 1 <= timestamp <= 10^9.

💡 Core Algorithmic Approaches

  1. Keep a hash map from message to the last timestamp at which it was printed.
  2. On each call, look up the message. If it is absent, or the stored timestamp is at least 10 seconds old, allow the print and update the map.
  3. Otherwise suppress it and return false.
  4. The window is inclusive of exactly 10 seconds, so the condition is timestamp - last >= 10, not > 10.

💻 Benchmark Python3 Implementation

class Logger:
    def __init__(self):
        self.last = {}                     # message -> last printed timestamp

    def shouldPrintMessage(self, timestamp: int, message: str) -> bool:
        last = self.last.get(message)
        if last is None or timestamp - last >= 10:   # never seen, or window elapsed
            self.last[message] = timestamp
            return True
        return False

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(1) per call: a single hash lookup and update.
💾 Space Complexity
O(k) where k is the number of distinct messages seen.

⚠️ Interview Pitfalls & Follow-ups

  • Using > 10 instead of >= 10: a message exactly 10 seconds later is allowed, since the window is 10 seconds long.
  • Storing a queue of all timestamps: unnecessary; only the most recent timestamp per message matters.
  • Assuming timestamps are strictly increasing: the statement says non-decreasing, so equal timestamps are possible and the same comparison handles them.
  • Updating the timestamp on a suppressed call: this would push the window forward and could starve a message indefinitely. Only update when the print is allowed.