Sliding Window Rate Limiter
Reported by candidates from ZipRecruiter's online assessment. Pattern, common pitfall, and the honest play if you blank under the timer.
The ZipRecruiter Sliding Window Rate Limiter, reported in October 2022, looks like a design question but it's really a per-key queue with eviction. Each organization gets its own list of allowed timestamps. For every request you drop the expired ones from the front, check the count against the limit, and either push or reject. That's the whole thing. The traps are the boundary (exactly windowSize old means expired) and the rule that rejected requests don't count. If you blank on the details during the live OA, StealthCoder is the invisible safety net that reads the prompt and hands you the structure.
The problem
For this exercise, use the callable contract below. You receive payment-transfer API requests in nondecreasing timestamp order. Each request has an organization identifier. For each request at time t, allow it when fewer than limit previously allowed requests for the same organization have timestamps strictly greater than t - windowSize. A previously allowed request exactly windowSize milliseconds old has expired. Rejected requests do not consume capacity. Return an array with 1 for every allowed request and 0 for every rejected request, preserving input order. Function allowedRequests(organizationIds: int[], timestamps: int[], limit: int, windowSize: int) → int[] Examples Example 1 organizationIds = [1,1,1,1] timestamps = [0,2,5,10] limit = 2 windowSize = 10 return = [1,1,0,1] The requests at times 0 and 2 fill the window. The request at 5 is rejected. At time 10, the accepted request at time 0 has expired, so the request is allowed. Example 2 organizationIds = [7,8,7,8,7] timestamps = [1,1,2,3,4] limit = 1 windowSize = 3 return = [1,1,0,0,1] Each organization has an independent window. The second request for each organization is rejected. At time 4, organization 7 may proceed because its accepted request at time 1 is exactly one window old. Example 3 organizationIds = [3,3,3,3] timestamps = [5,5,5,5] limit = 3 windowSize = 100 return = [1,1,1,0] Equal timestamps are processed in input order. The first three requests are accepted and the fourth is rejected. Constraints 1 ≤ organizationIds.length = timestamps.length ≤ 2 * 10^5. 1 ≤ organizationIds[i] ≤ 10^9. 0 ≤ timestamps[i] ≤ 10^9, and timestamps is nondecreasing. 1 ≤ limit ≤ 10^5. 1 ≤ windowSize ≤ 10^9.
Reported by candidates. Source: FastPrep
Pattern and pitfall
Use a hash map from organization id to a deque of accepted timestamps. For a request at time t, pop from the front while the front timestamp is less than or equal to t - windowSize. That's the strict boundary: only timestamps strictly greater than t - windowSize survive. Then if the deque size is below limit, append t and output 1. Otherwise output 0 and append nothing. Each timestamp is pushed once and popped at most once, so the total is O(n) with n up to 2 * 10^5. The common pitfall is using less than instead of less than or equal when evicting, which breaks Example 1 at time 10. Another is pushing rejected requests, which inflates the window. Don't share one deque across organizations. If the boundary logic slips under pressure, StealthCoder is the hedge on the live OA, since it works out the edge case from the examples while you type.
If you see this problem in your OA tomorrow, the play is to recognize the pattern in 30 seconds. StealthCoder buys you that recognition.
You can drill Sliding Window Rate Limiter cold, or you can hedge it. StealthCoder runs invisibly during screen share and surfaces a working solution in under 2 seconds. The proctor sees the IDE. They don't see what's behind it. Built by an Amazon engineer who passed his OA cold and still thinks the filter is broken.
Get StealthCoderRelated leaked OAs
You've seen the question.
Make sure you actually pass ZipRecruiter's OA.
ZipRecruiter reuses patterns across OAs. Built by an Amazon engineer who passed his OA cold and still thinks the filter is broken. Works on HackerRank, CodeSignal, CoderPad, and Karat.
Sliding Window Rate Limiter FAQ
What's the trick in the ZipRecruiter sliding window rate limiter?+
Keep a deque of accepted timestamps per organization in a hash map. Evict from the front while the timestamp is at most t - windowSize, then compare the size to limit. Each timestamp enters and leaves once, so the whole run is linear.
How do I handle the exact windowSize boundary?+
A request exactly windowSize old is expired. So evict when front <= t - windowSize. Check Example 1: at t=10 with window 10, the request at 0 is evicted, so the new request is allowed. Using strict less than fails that example.
Do rejected requests count toward the limit?+
No. Only allowed requests are stored in the deque. If you push a rejected timestamp, later requests get blocked wrongly. Output 0 and move on without touching the queue.
Is the complexity a problem with 2 * 10^5 requests?+
No, if you use a deque with amortized eviction. It's O(n) time overall. Scanning the whole history per request would be quadratic and risks timing out. Also don't use a list with pop(0) in Python, use collections.deque.
How do I prepare for this in 48 hours?+
Write it once from scratch with a dict of deques and run all three examples, especially the equal-timestamp case and the two-organization case. Then test limit=1 and a window of 1. That covers every edge this problem has.