Logger Rate Limiter

---

Intuition

Simply store in a hashmap the messages, and check the hashmap if the message has exceeded the threshold by checking whether it has been 10 minutes since last time.

Complexity

Runtime

$O(M)$ where M is the number of messages

Space

$O(M)$ where M is the number of messages

• Optimize with a queue of the messages

Code

class Logger:
    def __init__(self):
        self.hm = {}
 
    def shouldPrintMessage(self, timestamp: int, message: str) -> bool:
        if message in self.hm and timestamp - self.hm[message] < 10:
            return False
        self.hm[message] = timestamp
        return True
 
# Your Logger object will be instantiated and called as such:
# obj = Logger()
# param_1 = obj.shouldPrintMessage(timestamp,message)

Notes

Feedback

• The issue with this approach is that the hashmap gets too many keys. Therefore, you need a means to periodically clear out the keys that have not been used if you are past a certain number of them.
• During the interview, just pay very close attention to what he is asking rather than making up your own solutions.

Code from Actual Coding Interview

 
# foo: 11
# 
 
class Logger:
    def __init__(self) -> None:
        self.hm = {}
 
    def shouldPrintMessage(self, timestamp, message) -> bool:
        if message in self.hm and timestamp - self.hm[message] < 10:
            return False
        self.hm[message] = timestamp
        return True
        
logger = Logger()
a = logger.shouldPrintMessage(1, "foo")
b = logger.shouldPrintMessage(2, "bar")
c = logger.shouldPrintMessage(8, "bar")
d = logger.shouldPrintMessage(10, "foo")
e = logger.shouldPrintMessage(11, "foo")
print(a, b, c, d, e)
 
# 11: foo, 12: bar, 18: bar, 20: foo, 21: foo
# 1, 2, 8, 10, 11
 
# source_file = a.txt, message = 'hello', source_file = a.txt, message = 'hello'
 
# a: 12
# b: 15
# c: 3
 
# X = 15
# Y = 100

Cards

START Basic Front: Logger Rate Limiter Back: Keep adding to the END

---

References

• Logger Rate Limiter