Leetcode

Logger Rate Limiter

May 26, 2022 by aAshish

Approach 1: Queue + Set

  • Time:Constructor: O(1), shouldPrintMessage(timestamp: int, message: str): O(n)
  • Space:O(n)

C++

 
class Logger {
 public:
  bool shouldPrintMessage(int timestamp, string message) {
    // remove messages that are 10 secs from the current timestamp
    while (!messageQueue.empty()) {
      const auto [headTimestamp, headMessage] = messageQueue.front();
      if (timestamp < headTimestamp + 10)
        break;
      messageQueue.pop_front();
      messageSet.erase(headMessage);
    }

    if (messageSet.count(message))
      return false;

    messageQueue.emplace_back(timestamp, message);
    messageSet.insert(message);
    return true;
  }

 private:
  // [(timestamp, message)]
  deque<pair<int, string>> messageQueue;
  unordered_set<string> messageSet;
};

JAVA

 
class Logger {
  public boolean shouldPrintMessage(int timestamp, String message) {
    // remove messages that are 10 secs from the current timestamp
    while (!messageQueue.isEmpty()) {
      var head = messageQueue.peekFirst();
      if (timestamp - head.getKey() < 10)
        break;
      messageQueue.pollFirst();
      messageSet.remove(head.getValue());
    }

    if (messageSet.contains(message))
      return false;

    messageQueue.offerLast(new Pair<>(timestamp, message));
    messageSet.add(message);
    return true;
  }

  // [(timestamp, message)]
  private Deque<Pair<Integer, String>> messageQueue = new ArrayDeque<>();
  private Set<String> messageSet = new HashSet<>();
}

Python

 
class Logger:
  def __init__(self):
    # [(timestamp, message)]
    self.messageQueue = deque()
    self.messageSet = set()

  def shouldPrintMessage(self, timestamp: int, message: str) -> bool:
    # remove messages that are 10 secs from the current timestamp
    while self.messageQueue:
      headTimestamp, headMessage = self.messageQueue[0]
      if timestamp < headTimestamp + 10:
        break
      self.messageQueue.popleft()
      self.messageSet.remove(headMessage)

    if message in self.messageSet:
      return False

    self.messageQueue.append((timestamp, message))
    self.messageSet.add(message)
    return True

Approach 2: Map (unrealistic)

  • Time:Constructor: O(1), shouldPrintMessage(timestamp: int, message: str): O(1)
  • Space:O(|\texttt{shouldPrintMessage()}|)

C++

 
class Logger {
 public:
  bool shouldPrintMessage(int timestamp, string message) {
    if (timestamp < okTime[message])
      return false;

    okTime[message] = timestamp + 10;
    return true;
  }

 private:
  unordered_map<string, int> okTime;  // {message: ok time}
};

JAVA

 
class Logger {
  public boolean shouldPrintMessage(int timestamp, String message) {
    if (timestamp < okTime.getOrDefault(message, 0))
      return false;

    okTime.put(message, timestamp + 10);
    return true;
  }

  private Map<String, Integer> okTime = new HashMap<>(); // {message: ok time}
}

Python

 
class Logger:
  def __init__(self):
    self.okTime = {}  # {message: ok time}

  def shouldPrintMessage(self, timestamp: int, message: str) -> bool:
    if timestamp < self.okTime.get(message, 0):
      return False

    self.okTime[message] = timestamp + 10
    return True