Katkat
Back

Implement and Test a Sliding-Window Rate Limiter

SnowflakeSoftware Engineer · Onsite
MediumSoftware EngineerOnsiteSoftware Engineering Fundamentals

Last updated

This problem tests your ability to implement an efficient sliding-window algorithm and design a robust testing strategy for a stateful component.

Sliding-Window Rate Limiter

Implement an in-memory rate limiter that tracks requests per user based on a fixed time window. You need to provide a class RateLimiter that determines if a request is allowed based on the number of requests made by a specific key in the last N milliseconds.

Requirements

  • The constructor should accept max_requests (the limit) and window_size_ms (the duration of the sliding window).
  • Implement bool allow(str key, int timestamp): returns True if the request is permitted, False otherwise.
  • Use an efficient data structure to store timestamps for each key.

Constraints

  • Assume timestamp is an integer representing milliseconds.
  • Timestamps passed to allow will be monotonically increasing.
  • Performance: allow should ideally run in better than O(N) time relative to the number of requests in the window.

Example

# window_size = 1000ms, max_requests = 2
limiter = RateLimiter(2, 1000)

limiter.allow("user1", 100) # True
limiter.allow("user1", 500) # True
limiter.allow("user1", 800) # False (3rd request within 1000ms)
limiter.allow("user1", 1200) # True (window is now 200ms to 1200ms, only 2 requests in window)

Task

  1. Provide the implementation of RateLimiter.
  2. Describe how you would test this implementation, specifically focusing on edge cases like concurrent timestamps or large volumes of old, stale data.

Hints

Hint 1

Consider using a double-ended queue (deque) to store the timestamps of requests for each user, removing those that fall outside the current window.

Hint 2

Think about the memory complexity if a user sends millions of requests per second; is storing every single timestamp sustainable?

Hint 3

For testing, focus on boundary conditions where the time difference is exactly equal to the window size and scenarios involving gaps in request traffic.

Follow-up questions

  • How would you modify this implementation to work in a distributed system with multiple server nodes?
  • If we needed to limit requests at a granularity of 1ms, what data structures would help minimize memory usage?
  • How does your implementation handle a situation where a user tries to flood the system with invalid timestamps (e.g., timestamps from the past)?