Logger Rate Limiter

Patrick Leaton
Published: March 15, 2021, 8:45 p.m.
Problem Description

Design a logger system that receive stream of messages along with its timestamps, each message should be printed if and only if it is not printed in the last 10 seconds.

Given a message and a timestamp (in seconds granularity), return true if the message should be printed in the given timestamp, otherwise returns false.

It is possible that several messages arrive roughly at the same time.

Example:

Logger logger = new Logger();

// logging string "foo" at timestamp 1
logger.shouldPrintMessage(1, "foo"); returns true; 

// logging string "bar" at timestamp 2
logger.shouldPrintMessage(2,"bar"); returns true;

// logging string "foo" at timestamp 3
logger.shouldPrintMessage(3,"foo"); returns false;

// logging string "bar" at timestamp 8
logger.shouldPrintMessage(8,"bar"); returns false;

// logging string "foo" at timestamp 10
logger.shouldPrintMessage(10,"foo"); returns false;

// logging string "foo" at timestamp 11
logger.shouldPrintMessage(11,"foo"); returns true;

 

The description was taken from https://leetcode.com/problems/logger-rate-limiter/.

Problem Solution

#O(N) Time, O(N) Space
class Logger:
    def __init__(self):
        self.dictionary = {}
       
    def shouldPrintMessage(self, timestamp: int, message: str) -> bool:
        for i in list(self.dictionary):
            if timestamp - self.dictionary[i] >= 10:
                del self.dictionary[i]
            else:
                break
        if message not in self.dictionary:
            self.dictionary[message] = timestamp
            return True
        else:
            return False

Problem Explanation

The easiest way to solve this question is to handle each message request by seeing if it’s in a dictionary we'd make.  If it weren't, we'd place it there with its timestamp and return true.  If it were though, we’d see if the new timestamp minus the message’s timestamp value in the dictionary is greater than or equal to ten.  If it was greater than ten, we’d update the value to our current timestamp and say we could print the message.  If it was less than ten, then we’d return false.

This solution would be constant time retrieval but would take a ton of space since we aren’t doing anything with old messages that aren't being updated.

For a better trade-off of time for space, before we add any new message to the dictionary, we will first go through and delete any old messages.  Since the messages are given in chronological order, we will be able to nip the old slice of the dictionary in a fairly optimal time because we'd only have to search the prefix of the dictionary list for old values and can stop whenever we see new ones.

Let's start by initializing our dictionary.

    def __init__(self):
        self.dictionary = {}

 

Next, let's iterate through the beginning of our dictionary to search values that are ten or more seconds before our current timestamp. We can delete them so that we aren't wasting memory.  Once we are within our ten-second window and have no more old messages, we will break.

        for i in list(self.dictionary):
            if timestamp - self.dictionary[i] >= 10:
                del self.dictionary[i]
            else:
                break

 

Next, we’ll just need to check if the message is in our dictionary. 

        if message not in self.dictionary:

 

If it isn’t, we’ll place it there with the current timestamp and return true because this is the first time we are printing it within a ten-second window. 

        if message not in self.dictionary:
            self.dictionary[message] = timestamp
            return True

 

If it is, we’ll return false because that will mean it isn’t older than ten seconds and can't be printed within the current ten-second window.

        else:
            return False