Implement a thread-safe rate limiter
Company: Snapchat
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
Design and implement a per-user API rate limiter.
Requirements:
- Method: `boolean allow(String userId, long nowMillis)` returns whether the request is allowed at time `nowMillis`.
- Policy: allow at most **N** requests per **W** milliseconds per user.
- Choose any standard algorithm (e.g., fixed window, sliding window, token bucket).
Follow-ups:
- How do you make it safe under concurrency (multiple threads calling `allow` for the same `userId`)?
- Discuss tradeoffs between using locks vs lock-free/low-lock approaches (e.g., `ConcurrentHashMap`, atomics) and performance implications.
Quick Answer: This question evaluates a candidate's ability to design and implement a thread-safe per-user API rate limiter, focusing on concurrency control, synchronization techniques, and time-based request accounting in the Coding & Algorithms domain.
For each (user,time) request, allow at most limit requests per user in the previous window_ms interval.
Constraints
- requests are processed in arrival order
Examples
Input: ([('u', 0), ('u', 10), ('u', 20)], 2, 100)
Expected Output: [True, True, False]
Explanation: Third rejected.
Input: ([('u', 0), ('v', 1), ('u', 100)], 2, 100)
Expected Output: [True, True, True]
Explanation: Boundary evicts old request.
Input: ([], 2, 100)
Expected Output: []
Explanation: No requests.
Hints
- Use one deque of accepted timestamps per user.