Message Rate Limiter

Question

Design a message rate limiter that restricts the number of messages sent in a given time period.

Codemia · Accepted Answer

To design a message rate limiter, we need to ensure that a user can only send a specified number of messages within a defined time window. This is crucial in applications like APIs to prevent abuse and ensure fair usage among users.

We can use a sliding window algorithm to track the number of messages sent by each user. We'll maintain a queue to store timestamps of sent messages and check against the current time to enforce the rate limit.

Here is a simple implementation in Python:

```python
from collections import deque
import time

class RateLimiter:
    def __init__(self, limit, window):
        self.limit = limit
        self.window = window
        self.timestamps = deque()

def allow_message(self):
        current_time = time.time()
        # Remove timestamps older than the window
        while self.timestamps and self.timestamps[0] < current_time - self.window:
            self.timestamps.popleft()
        
        if len(self.timestamps) < self.limit:
            self.timestamps.append(current_time)
            return True
        return False
```
This code defines a `RateLimiter` class that allows a specified number of messages within a time window.

The time complexity of the `allow_message` method is O(1) for adding a message and O(n) for removing old timestamps, where n is the number of messages in the queue. The space complexity is O(n) as we store timestamps in a deque.

We must consider edge cases such as when the user sends messages at the exact limit or when messages are sent just before and after the window expires. Properly handling these will ensure that our rate limiter behaves as expected under all conditions.

Message Rate Limiter

Amazon

What the Interviewer Expects

Key Topics to Cover

How to Approach This

Possible Follow-up Questions

Sharpen Your Skills on Codemia

Sample Answer

Framing

Approach

Submit Your Answer

Amazon Software Engineer Interview Guide

Related Questions

Binary Search on graph

Count kth largest element in array

Find connected components in string

Merge Three Sorted strings

Binary Search on string