Per-User Sliding-Window Rate Limiter
Updated
Problem statement
You are building a rate limiter. Request i comes from the user users[i] at second times[i]. The requests are given in time order, so times never decreases, and requests in the same second are handled in their input order.
Each user may have at most k allowed requests in any window of t seconds. Handle the requests one by one. Request i is allowed if its user has fewer than k allowed earlier requests that are less than t seconds old, that is, at a time p with times[i] - p < t. Otherwise it is rejected.
- A request that is exactly
tseconds old no longer counts. Put another way, anytwhole seconds in a row hold at mostkallowed requests of one user. - Rejected requests never count toward the limit.
- Every user has a separate limit.
Return an array results where results[i] is 1 if request i is allowed and 0 if it is rejected.
Function
limitRequests(users: String[], times: int[], k: int, t: int) → int[]Examples
Example 1
users = ["alice","bob","alice","alice","bob","alice"]times = [1,2,3,5,6,11]k = 2t = 10return = [1,1,1,0,1,1]- Requests 0 and 2 from
"alice"(seconds1and3) are allowed, because she has fewer than2recent allowed requests each time. - Request 3 from
"alice"at second5is rejected: her requests at1and3are less than10seconds old, so she already has2. "bob"has his own limit, so his requests at2and6are both allowed.- Request 5 from
"alice"at second11is allowed: the request at1is now exactly10seconds old and no longer counts, so only the one at3is recent.
Example 2
users = ["u","u","u","u"]times = [0,0,1,2]k = 1t = 2return = [1,0,0,1]- The request at second
0is allowed. The second request at second0and the one at second1are rejected, because the allowed request at0is less than2seconds old. - At second
2, the allowed request at0is exactly2seconds old and no longer counts. - The rejected requests at
0and1never count, so the last request is allowed.
Example 3
users = ["a","b","a","b","a"]times = [7,7,7,7,7]k = 2t = 1return = [1,1,1,1,0]- All five requests come in the same second, in the given order.
"a"gets its first2requests allowed and its third rejected, and"b"gets both of its requests allowed.
Constraints
1 <= users.length <= 2000times.length == users.lengthusers[i]has 1 to 10 characters, and each one is a lowercase English letter.0 <= times[i] <= 10^9times[i - 1] <= times[i]for everyi >= 11 <= k <= 20001 <= t <= 10^9
More PayPal interview questions
- Minimum Cost to Merge Values into OneOA · Seen Nov 2026
- Total Cost Against the Lowest Earlier PriceOA · Seen Nov 2026
- Items Purchase (For Java Backend Engineer)OA · Seen Nov 2024
- Find Minimum Price to SpendOA · Seen Oct 2024
- Modify ArrayOA · Seen Jun 2024
- Count User Logins 🌿 (Singapore)OA · Seen Mar 2024
- Similar Password 🪴 (Singapore)OA · Seen Mar 2024
- Can the Singer Perform the Song?PHONE SCREEN · Seen Jul 2025
Similar questions at other companies
- Incident MonitorStripe · OAStripe interview questions
- Per-Client Sliding-Window Rate LimiterGeneral Motors · OA
- Rate Limiter Sliding Window With Per-Entity LimitsRoblox · PHONE SCREEN · ONSITE INTERVIEWRoblox interview questions
- Metric Counter with a Fake ClockSnap Inc. · ONSITE INTERVIEWSnap Inc. interview questions
- Per-Client Sliding-Window Rate LimiterNike, Inc. · ONSITE INTERVIEWNike, Inc. interview questions
- Key-Value Store GET and PUT QPSDatabricks · PHONE SCREENDatabricks interview questions
- Duplicate News Within 60 SecondsBloomberg LP · PHONE SCREENBloomberg LP interview questions
- Completions API Rate LimiterCursor · PHONE SCREENCursor interview questions
- Get Minimum Time for DNS ResolutionWalleye Capital · OA
- Get Minimum Time for DNS Resolution (for Data Science Developer)IBM · OAIBM interview questions