Logger Rate Limiter
Statement
Given a stream of message requests and their timestamps as input, implement a logger rate limiter system that decides whether the current message request is displayed. The decision depends on whether the same message has already been displayed in the last s seconds. If yes, then the decision is false, as the message is considered a duplicate. Otherwise, the decision is true.
Constraints
- 1 ≤
request.length()≤ 10² - 0 ≤
timestamp≤ 10³ - Timestamps are in ascending order
- Messages can be written in lowercase and uppercase English characters
Solution
"""
production algorithm
"""
class RequestLogger:
def __init__(self, limit):
self.map = {}
self.limit = limit
def message_request_decision(self, timestamp, request):
"""
time complexity O(1)
space complexity O(n)
"""
if request in self.map:
if timestamp - self.map[request] < self.limit:
return False
self.map[request] = timestamp
return True"""
unit tests
"""
from unittest import TestCase
from algorithms.hashmaps.logger_rate_limiter.request_logger import RequestLogger
class RequestLoggerTestCase(TestCase):
def test_decision_is_false(self):
# Given
limit = 5
logger = RequestLogger(limit)
messages = [(1, "Hello"), (2, "Hello"), (3, "Hello"),
(4, "Hello"), (5, "Hello")]
# When
actual = [logger.message_request_decision(
timestamp, message) for timestamp, message in messages]
# Then
expected = [True, False, False, False, False]
self.assertEqual(actual, expected)
def test_decision_is_true(self):
# Given
limit = 5
logger = RequestLogger(limit)
messages = [(10, "Hello"), (20, "Hello"), (30, "Hello"),
(40, "Hello"), (50, "Hello")]
# When
actual = [logger.message_request_decision(
timestamp, message) for timestamp, message in messages]
# Then
expected = [True, True, True, True, True]
self.assertEqual(actual, expected)Strategy
Hash Maps.
Explanation
The data structure uses a hash map to hold the messages, and the timestamps of when each message was received. If the same message is received multiple times within the time limit, then the decision is false. Otherwise, the decision is true.
Time Complexity
The time complexity of the algorithm is O(1).
Space Complexity
Let n be the number of messages received. At worst, every message becomes a new key in the dictionary. Therefore, the auxiliary space complexity of the algorithm is O(n).
