Rate Limiter with Global and Per-User Limits
Updated
Problem statement
You are building a rate limiter for an API. Request i arrives at time timestamps[i] from user userIds[i]. Requests come in the order given, and requests with the same time are handled in that order.
The limiter has two limits that use the same time window of length windowSize:
- Global limit: at most
globalLimitallowed requests in total. - Per-user limit: at most
userLimitallowed requests from any one user.
For a request at time t, the window holds the earlier allowed requests whose time is greater than t - windowSize. A request exactly windowSize time units old is no longer in the window. The request is allowed only if the window holds fewer than globalLimit allowed requests in total and fewer than userLimit allowed requests from the same user. Otherwise it is rejected.
Only allowed requests count toward the limits. A rejected request uses no room, neither for its user nor globally.
Return a boolean array where element i is true if request i is allowed and false if it is rejected.
Function
rateLimitRequests(timestamps: int[], userIds: String[], windowSize: int, userLimit: int, globalLimit: int) → boolean[]Examples
Example 1
timestamps = [1,2,3,5,11,12]userIds = ["a","a","a","b","b","c"]windowSize = 10userLimit = 2globalLimit = 3return = [true,true,false,true,true,true]The window is 10, so a request at time t looks at allowed requests with times greater than t - 10.
- Times 1 and 2:
ais allowed twice. - Time 3:
aalready has 2 allowed requests in the window, which is its limit, so it is rejected. The rejection does not use up any space. - Time 5: there are 2 allowed requests in the window overall and
bhas none, so it is allowed. The window now holds 3 allowed requests. - Time 11: the window is times greater than 1, so the request at time 1 has dropped out. 2 allowed requests remain, and
bhas 1, so it is allowed. - Time 12: the request at time 2 drops out. The window holds 2 allowed requests and
chas none, so it is allowed.
Example 2
timestamps = [0,0,0,0,5]userIds = ["x","y","z","x","w"]windowSize = 5userLimit = 2globalLimit = 3return = [true,true,true,false,true]The first three requests at time 0 fill the global limit of 3. The fourth request comes from x, which has only 1 allowed request, but the global limit is full, so it is rejected.
At time 5 the window is times greater than 0, so all three earlier allowed requests are outside it, and w is allowed.
Example 3
timestamps = [1,2,3,4]userIds = ["u","u","u","u"]windowSize = 3userLimit = 1globalLimit = 5return = [true,false,false,true]u may have 1 allowed request in any window of 3. Time 1 is allowed. Times 2 and 3 still see the request at time 1 and are rejected.
At time 4 the window is times greater than 1, so the request at time 1 is gone. The two rejected requests never counted, so time 4 is allowed.
Constraints
1 <= timestamps.length <= 3000userIds.length == timestamps.length0 <= timestamps[i] <= 10^9timestampsis sorted in non-decreasing order.- Each
userIds[i]has1to10lowercase English letters. 1 <= windowSize <= 10^91 <= userLimit <= globalLimit <= 3000
More OpenAI Onsite Interview questions
- Sparse Plant Infection SimulationPHONE SCREEN · ONSITE INTERVIEW · Seen Nov 2026
- Rectangle Point Coverage CountsPHONE SCREEN · ONSITE INTERVIEW · Seen Nov 2026
- Message Event AggregationPHONE SCREEN · ONSITE INTERVIEW · Seen Oct 2026
- 15-Minute Chat Session TrackerPHONE SCREEN · ONSITE INTERVIEW · Seen Oct 2026
- Segmented Durable Key-Value StorePHONE SCREEN · ONSITE INTERVIEW · Seen Oct 2026
- Durable Work Queue OperationsPHONE SCREEN · ONSITE INTERVIEW · Seen Oct 2026
- Versioned Social NetworkPHONE SCREEN · ONSITE INTERVIEW · Seen Oct 2026
- Budgeted API Inference with Out-of-Order FeedbackONSITE INTERVIEW · Seen Oct 2026
- Plant Infection Simulation, Part 4: Death CountdownPHONE SCREEN · ONSITE INTERVIEW · Seen Oct 2026
- Count Friend CirclesPHONE SCREEN · ONSITE INTERVIEW · Seen Oct 2026
Similar questions at other companies
- Sliding-Window Rate LimiterAmazon · ONSITE INTERVIEW
- Per-Element Hit CounterUber · ONSITE INTERVIEWUber 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
- Sliding-Window Rate LimiterStripe · PHONE SCREEN · ONSITE INTERVIEWStripe interview questions
- Transaction Authorizer with Velocity RulesGoldman Sachs · ONSITE INTERVIEWGoldman Sachs interview questions
- Per-Client API Rate LimiterDocker · PHONE SCREEN
- Per-Client Sliding-Window Rate LimiterCVS Health · PHONE SCREEN
- Delayed Streaming Duplicate SuppressionGoogle · PHONE SCREENGoogle interview questions
- Per-Client Sliding-Window Rate LimiterGeneral Motors · OA