Completions API Rate Limiter
Problem statement
You are building a rate limiter for an API. You get a log of n requests. Request i was sent by user userIds[i] to the endpoint urls[i], has a body of bodySizes[i] bytes, and arrived at second timestamps[i].
Go through the requests one at a time, in the order given. Each request is either accepted or denied by the rules below. Return a boolean array answer where answer[i] is true if request i is accepted and false if it is denied.
Rules
Every rule is checked per user: only the same user's earlier accepted requests count.
| Rule | Applies to | Limit |
|---|---|---|
| 1 | v1/completions/standard | at most 3 requests in the last 1 second |
| 2 | v1/completions/chunked | at most 7 requests in the last 60 seconds |
| 3 | v2/completions/chunked | at most 5 requests in the last 1 second |
| 4 | v1/completions/chunked | at most 100 bytes of body in total in the last 60 seconds |
| 5 | every endpoint | at most 7 requests in the last 3600 seconds |
How the rules work
- Rules 1 to 4 apply only when
urls[i]is exactly the endpoint in the table. Rule 5 applies to every request, so any other endpoint, such asv1/models, is limited only by rule 5. - For a request at second
t, the lastWseconds means the times greater thant - Wand up tot. An accepted request from exactlyWseconds earlier no longer counts. For a 1-second rule, this means only requests from the same second count. - A count rule with a limit of
Lpasses if, in its window, the user has fewer thanLaccepted requests that the rule applies to. - Rule 4 passes if the body sizes of the user's accepted
v1/completions/chunkedrequests in the window, plus the new request's own body size, add up to at most 100. - A request is accepted only if every rule that applies to it passes. If even one rule fails, the request is denied, and it never counts toward any rule later, not even the rules it passed.
- Requests with the same timestamp are handled in array order.
Function
processRequests(userIds: String[], urls: String[], bodySizes: int[], timestamps: int[]) → boolean[]Examples
Example 1
userIds = ["a","a","a","a","b","a"]urls = ["v1/completions/standard","v1/completions/standard","v1/completions/standard","v1/completions/standard","v1/completions/standard","v1/completions/standard"]bodySizes = [5,5,5,5,5,5]timestamps = [10,10,10,10,10,11]return = [true,true,true,false,true,true]All six requests go to v1/completions/standard, so rule 1 (3 per second) applies, and rule 5 applies as always.
- User
asends three requests at second10. All are accepted. - The fourth request from
aat second10would make 4 in the same second, so it is denied. - User
bhas no requests yet. Limits are per user, so its request at second10is accepted. - At second
11, the last 1 second holds only times greater than10, so userahas 0 requests there and is accepted again. Counting this one, userahas 4 accepted requests in the last hour, so rule 5 passes too.
Example 2
userIds = ["u1","u1","u1","u1","u1"]urls = ["v1/completions/chunked","v1/completions/chunked","v1/completions/chunked","v1/completions/chunked","v1/completions/chunked"]bodySizes = [60,50,40,1,30]timestamps = [0,20,30,59,60]return = [true,false,true,false,true]Every request goes to v1/completions/chunked, so rule 4 (at most 100 bytes in the last 60 seconds) decides here. Rules 2 and 5 never come close.
- Second
0: 60 bytes. Accepted, 60 bytes in the window. - Second
20:60 + 50 = 110, which is over 100. Denied, and its 50 bytes do not count. - Second
30:60 + 40 = 100, which is not over 100. Accepted. - Second
59:100 + 1 = 101. Denied. - Second
60: the window holds times greater than0, so the 60-byte request has left. Only the 40-byte request is still inside, and40 + 30 = 70. Accepted.
Example 3
userIds = ["x","x","x","x","x","x","x","x","x","x"]urls = ["v2/completions/chunked","v2/completions/chunked","v2/completions/chunked","v2/completions/chunked","v2/completions/chunked","v2/completions/chunked","v1/models","v1/completions/standard","v1/models","v1/models"]bodySizes = [0,0,0,0,0,0,0,0,0,0]timestamps = [100,100,100,100,100,100,200,300,3699,3700]return = [true,true,true,true,true,false,true,true,false,true]- The first five
v2/completions/chunkedrequests at second100are accepted. The sixth is denied by rule 3 (5 per second). v1/modelshas no rule of its own, but rule 5 counts every endpoint. It is accepted at second200, and thev1/completions/standardrequest at second300is accepted too. Userxnow has 7 accepted requests.- At second
3699, the last 3600 seconds are times greater than99. All 7 accepted requests are inside, so it is denied by rule 5. - At second
3700, the window is times greater than100. The five requests from second100have left, so only 2 remain, and the request is accepted.
Constraints
1 <= userIds.length <= 1000urls.length == bodySizes.length == timestamps.length == userIds.length1 <= userIds[i].length <= 10userIds[i]contains only lowercase English letters and digits.1 <= urls[i].length <= 30urls[i]contains only lowercase English letters, digits, and/.0 <= bodySizes[i] <= 10000 <= timestamps[i] <= 10^9timestampsis sorted in non-decreasing order.