Rate Limiter
Allow at most N requests in any 10-second window โ the logic behind every API.
๐งฉ Problem statement
Requests arrive at increasing times (in seconds). Allow at most LIMIT requests in any window of 10 seconds: a request at time T is allowed if fewer than LIMIT allowed requests happened in (T โ 10, T]. Show ALLOW or BLOCK for each request.
๐ Requirements
- Time windows
- Counters
- State
- Queue of timestamps
๐ฅ Inputs
- LIMIT
- REQUEST_TIMES: list of request times
๐ค Outputs
- ALLOW / BLOCK per request
๐ Rules
- Window: the last 10 seconds, (T โ 10, T]
- Blocked requests donโt count
๐ง Constraints
- Times are in increasing order
๐งญ Suggested approach
- Keep a queue of the times of allowed requests
- Remove old times from the front
- Allow if the queue has room
๐ง Required concepts
- Queues
- Loops
- State
Design your solution here. Use Run to dry-run it step by step and Run tests to check it. Hints unlock one at a time โ try on your own first!
๐งช Edge cases to test
- Requests exactly 10 seconds apart
- LIMIT = 1
- A burst of many requests at the same time
๐ Complexity analysis
Each request is added and removed at most once: O(n) total. Memory O(LIMIT).
๐ Solution walkthrough (open after youโve tried!)
The queue holds the times of recent allowed requests, oldest at the front. Before judging a new request, times that have left the 10-second window are dropped from the front. If fewer than LIMIT remain, the request is allowed and its time is queued; otherwise itโs blocked.
๐ Challenge extensions
- A different limit per user (map of queues)
- Report how long until the next request is allowed
- A token-bucket version
