Sliding Window Rate Limiter
Updated
Problem statement
Build a rate limiter that lets each client make at most limit requests in any time window of length window.
Request i comes from client clientIds[i] at time timestamps[i]. The requests are given in time order, and requests with the same time are handled in the order given. A request at time t is allowed if, counting only earlier requests from the same client that were allowed, fewer than limit have a time greater than t - window. In other words, the window covers the times from t - window + 1 through t. Otherwise the request is rejected.
A rejected request does not count against the client later. Different clients never affect each other. Return an array whose i-th value is true if request i is allowed and false if it is rejected.
Function
rateLimit(limit: int, window: int, clientIds: String[], timestamps: int[]) → boolean[]Examples
Example 1
limit = 2window = 10clientIds = ["amy","amy","amy","amy"]timestamps = [1,5,9,11]return = [true,true,false,true]Times 1 and 5 are allowed. At time 9 the window covers times 0 through 9, which already holds 2 allowed requests, so it is rejected. At time 11 the window covers 2 through 11: only the request at 5 is inside, so it is allowed.
Example 2
limit = 1window = 3clientIds = ["bo","cy","bo","bo","cy"]timestamps = [0,0,2,3,3]return = [true,true,false,true,true]With limit = 1 and window = 3, bo is allowed at time 0. At time 2 the window covers 0 through 2, so bo is rejected. At time 3 the window covers 1 through 3; the request at 0 has left it and the rejected one at 2 does not count, so bo is allowed. Client cy is counted separately: allowed at 0 and again at 3.
Example 3
limit = 2window = 5clientIds = ["x","x","x","x","x"]timestamps = [0,1,2,5,6]return = [true,true,false,true,true]Times 0 and 1 are allowed and 2 is rejected. At time 5 the window covers 1 through 5: the request at 0 has left, so only one allowed request remains and this one is allowed. At time 6 the window covers 2 through 6 and holds the allowed requests at 5 only, because the one at 2 was rejected, so it is allowed.
Constraints
1 <= limit <= 5001 <= window <= 10^61 <= clientIds.length == timestamps.length <= 1000- Each
clientIds[i]has1to10lowercase English letters. 0 <= timestamps[i] <= 10^9, andtimestampsnever decreases.
More LotusFlare Onsite Interview questions
Similar questions at other companies
- Sliding-Window Rate LimiterAmazon · ONSITE INTERVIEW
- Rate Limiter with Global and Per-User LimitsOpenAI · ONSITE INTERVIEWOpenAI interview questions
- 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
- Article Vote TrackerRippling · PHONE SCREEN · ONSITE INTERVIEWRippling interview questions
- Sliding-Window Rate LimiterStripe · PHONE SCREEN · ONSITE INTERVIEWStripe interview questions
- Restaurant Waitlist with Exact-Size TablesGoogle · ONSITE INTERVIEWGoogle interview questions
- Matching Engine with Order CancellationIMC Trading · ONSITE INTERVIEWIMC Trading interview questions
- Transaction Authorizer with Velocity RulesGoldman Sachs · ONSITE INTERVIEWGoldman Sachs interview questions