Katkat
Back

Implement a sliding-window rate limiter allow()

MicrosoftSoftware Engineer · Onsite
HardSoftware EngineerOnsiteCoding & Algorithms

Last updated

This problem tests your ability to implement a thread-safe rate limiter using a sliding window algorithm to ensure a service stays within specified traffic constraints.

Problem Statement

Implement a RateLimiter class that restricts the number of requests a user can make within a rolling time window. You need to support a sliding window approach rather than a fixed window to prevent bursts of traffic at window boundaries.

Requirements

  • RateLimiter(int capacity, int window_size_seconds): Initializes the rate limiter with a maximum of capacity requests allowed per window_size_seconds window.
  • allow(int user_id): Returns True if the request is allowed, and False otherwise.

Constraints

  • The solution should handle multiple threads concurrently.
  • Time complexity for allow() should be better than O(N), where N is the number of requests in the window.
  • You may assume time.time() provides the current timestamp in seconds.

Example

# Capacity 2, Window 5 seconds
limiter = RateLimiter(2, 5)

print(limiter.allow(1)) # True
print(limiter.allow(1)) # True
print(limiter.allow(1)) # False (exceeds capacity)
# After 5 seconds pass...
print(limiter.allow(1)) # True

Considerations

  • How will you store the history of timestamps for each user?
  • How do you efficiently remove expired entries?
  • Ensure the implementation is thread-safe using appropriate locking mechanisms.

Hints

Hint 1

Use a hash map to store a deque or list of timestamps for each user_id.

Hint 2

When `allow()` is called, remove all timestamps from the user's deque that are older than `current_time - window_size`.

Hint 3

After cleaning up, check if the size of the deque is less than the capacity before adding the new timestamp.

Follow-up questions

  • How would you adapt this implementation to work in a distributed system with multiple server nodes?
  • What is the memory complexity of this approach if a user sends 1,000 requests per second?
  • How could you optimize space if the capacity is very large, perhaps using a different algorithm like Token Bucket?