Home
Algorithms Data Structures Interview Experiences
Amazon Google Facebook Microsoft Apple Netflix
Play 2048 How to

LeetCode Solutions

359. Logger Rate Limiter

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

Space: $O(n)$

			


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;
};




			


class Logger {
  public boolean shouldPrintMessage(int timestamp, String message) {
    // Remove messages that are 10 secs from the current timestamp
    while (!messageQueue.isEmpty()) {
      Pair<Integer, String> 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<>();
}




			


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