Katkat
Back

Implement sliding-window rate limiter function

AtlassianSoftware Engineer · Technical Screen
MediumSoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

This problem tests your ability to design a thread-safe rate limiter using a sliding window approach, focusing on time complexity optimization and memory management.

Problem Statement

Implement a RateLimiter class that restricts the number of requests a user can make within a rolling time window. You must track requests per user and allow or deny incoming requests based on a defined threshold.

Requirements

  • allow_request(user_id: str) -> bool: Returns True if the request is within the limit, False otherwise.
  • The rate limit is defined by a capacity N (maximum requests) and a time window T (in seconds).
  • Your implementation must be thread-safe.

Constraints

  • Time window T can range from 1 to 3600 seconds.
  • Capacity N can range from 1 to 10,000.
  • user_id is a string identifier.
  • Efficiency: The allow_request method should be as close to O(1) as possible.

Example

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

limiter.allow_request("user1") # True
limiter.allow_request("user1") # True
limiter.allow_request("user1") # False (limit reached)
# ... after 5 seconds ...
limiter.allow_request("user1") # True

Edge Cases

  • Rapid-fire requests within the same millisecond.
  • Handling users who have not made any requests yet.
  • Memory consumption if millions of unique user_ids are tracked.

Hints

Hint 1

Consider using a deque or a sorted list to store the timestamps of requests for each user, removing those that fall outside the current time window.

Hint 2

For O(1) performance, you could use a collections.deque or a linked list, but ensure you are removing expired timestamps before counting the current requests.

Hint 3

Since the check needs to be thread-safe, consider using a Lock or a Thread-safe wrapper when modifying the internal data structures for a specific user.

Follow-up questions

  • How would you modify this to support a distributed system where rate limiting needs to be synchronized across multiple server instances?
  • If memory is a concern, how can we prune old users or data that have not made a request in a long time?
  • Instead of an exact sliding window, could you implement a 'Token Bucket' or 'Leaky Bucket' algorithm? What are the trade-offs in terms of precision and implementation complexity?