Per-Client API Rate Limiter
Updated
Problem statement
You are building an API rate limiter that stops each client from sending too many requests in a short time. Every client is identified by an id (such as an IP address or an API key), and every client has its own limit: at most maxRequests accepted requests in any window of windowSize time units.
Requests arrive in order: request i comes from client clientIds[i] at time timestamps[i]. A request at time t is accepted if the same client has fewer than maxRequests accepted requests with a time in the window (t - windowSize, t]; otherwise it is rejected. Rejected requests do not count toward later decisions.
Return an array whose i-th value is true if request i is accepted and false if it is rejected.
Function
rateLimit(maxRequests: int, windowSize: int, clientIds: String[], timestamps: int[]) → boolean[]Examples
Example 1
maxRequests = 2windowSize = 10clientIds = ["a","a","b","a","a"]timestamps = [1,2,3,5,11]return = [true,true,true,false,true]- Client
ais accepted at times 1 and 2. At time 5 it already has 2 accepted requests in(-5, 5], so the request is rejected. - Client
bhas its own limit, so its request at time 3 is accepted. - At time 11 the window is
(1, 11]: the request at time 1 has left it and only the one at time 2 remains, soais accepted again.
Example 2
maxRequests = 1windowSize = 5clientIds = ["x","x","x"]timestamps = [0,4,5]return = [true,false,true]- The request at time 4 is rejected because time 0 is inside
(-1, 4]. - At time 5 the window is
(0, 5], which no longer contains time 0, and the rejected request at time 4 does not count, so it is accepted.
Example 3
maxRequests = 3windowSize = 100clientIds = ["k"]timestamps = [42]return = [true]- A single request is always accepted.
Constraints
1 <= maxRequests <= 10001 <= windowSize <= 1091 <= clientIds.length == timestamps.length <= 2000- Each
clientIds[i]is 1 to 10 lowercase English letters or digits. 0 <= timestamps[i] <= 109timestampsis sorted in non-decreasing order.
Similar questions at other companies
- Per-Client Sliding-Window Rate LimiterCVS Health · PHONE SCREEN
- Sliding-Window Rate LimiterUber · PHONE SCREENUber interview questions
- Recent Advertisement Click CountsAmazon · PHONE SCREEN
- Delayed Streaming Duplicate SuppressionGoogle · PHONE SCREENGoogle interview questions
- Completions API Rate LimiterCursor · PHONE SCREENCursor interview questions
- Sliding-Window Rate LimiterStripe · PHONE SCREEN · ONSITE INTERVIEWStripe interview questions
- Key-Value Store GET and PUT QPSDatabricks · PHONE SCREENDatabricks interview questions
- Rate Limiter with Global and Per-User LimitsOpenAI · ONSITE INTERVIEWOpenAI interview questions
- Per-Client Sliding-Window Rate LimiterGeneral Motors · OA
- Metric Counter with a Fake ClockSnap Inc. · ONSITE INTERVIEWSnap Inc. interview questions