Implement a Leaky Bucket Limiter
Company: Snapchat
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: hard
Interview Round: Onsite
Design and implement an in-memory leaky-bucket rate limiter.
A limiter is configured with:
- `capacity`: the maximum amount of queued load the bucket can hold
- `leak_rate`: how many units drain from the bucket per second
Each incoming request contributes 1 unit to the bucket. When a request arrives:
1. First, reduce the current bucket level based on how much time has elapsed since the last update.
2. If adding the new request would keep the bucket level at or below `capacity`, accept the request and update the bucket level.
3. Otherwise, reject the request.
Implement a thread-safe API such as `allow_request()` for use in a multithreaded server.
Follow-up discussion:
- How would you make the implementation safe under high concurrency?
- What synchronization strategy would you use, and what are the trade-offs?
- How would you handle time precision, bursty traffic, and clock-related edge cases?
- How would you scale this design if many application instances must share the same rate limit?
Quick Answer: This question evaluates understanding of rate-limiting algorithms (leaky bucket), concurrent programming, time-based state management, and thread-safe API design.
Given request timestamps, return whether each request is allowed by a leaky bucket with the configured capacity and leak rate.
Constraints
- Inputs are Python literals matching the function signature.
- Return a deterministic exact-match value.
Examples
Input: (2, 1.0, [0,0,0])
Expected Output: [True, True, False]
Explanation: Only two immediate requests fit capacity 2.
Input: (2, 1.0, [0,0,1,2])
Expected Output: [True, True, True, True]
Explanation: Leaking over time allows later requests.
Input: (1, 0.5, [0,1,2])
Expected Output: [True, False, True]
Explanation: Partial leaks accumulate.
Hints
- Clarify edge cases before coding.
- Keep the return value deterministic.