Problem · Array
Sliding-Window Rate Limiter
Learn this problem● Medium
SnowflakeFULLTIMEONSITE INTERVIEW
See Snowflake hiring insightsSnowflakeFULLTIMEONSITE INTERVIEWProblem statement
Process request timestamps requestTimes in their given order. For every request at time t, allow it only when fewer than limit previously allowed requests have timestamps in the half-open interval (t - windowSeconds, t].
- An allowed request consumes one slot in the window.
- A rejected request is dropped immediately and does not consume a slot.
- Timestamps are nondecreasing. Requests with the same timestamp are processed in input order.
Return one boolean per request, where true means allowed and false means rejected.
Function
acceptRequests(requestTimes: int[], limit: int, windowSeconds: int) → boolean[]Examples
Example 1
requestTimes = [1,2,3,4,7]limit = 3windowSeconds = 5return = [true,true,true,false,true]The request at time 4 is rejected because three allowed requests remain in its window. At time 7, the request at time 2 is excluded by the open left boundary, so one slot is available.
Example 2
requestTimes = [10,10,10,10]limit = 2windowSeconds = 3return = [true,true,false,false]Equal-time requests are processed in order. The first two consume the available slots; rejected requests do not change the window.
Example 3
requestTimes = []limit = 1windowSeconds = 1return = []An empty request stream produces an empty decision array.
Constraints
0 <= requestTimes.length <= 2000000 <= requestTimes[i] <= 10^9requestTimesis nondecreasing.1 <= limit <= 2000001 <= windowSeconds <= 10^9