Bounded Token-Bucket Request Queue
Learn this problem
PlaidFULLTIMEONSITE INTERVIEWProblem statement
You receive requests at the nondecreasing integer times in arrivalTimes. A token bucket is full with capacity tokens at time 0. One token is refilled at every positive multiple of refillInterval, up to capacity. Processing one request consumes one token.
When a request arrives, process it immediately if a token is available. Otherwise, append it to one FIFO queue when the queue contains fewer than maxQueue requests; if the queue is full, drop the request. Each refill first processes the oldest queued request immediately, if one exists, instead of storing that token. Refills occur before arrivals at the same time, and arrivals sharing a time are handled in input order.
After the final arrival, continue refilling until every queued request is processed. Return each request's processing time in input order, using -1 for a dropped request.
Function
scheduleRateLimitedRequests(arrivalTimes: int[], capacity: int, refillInterval: int, maxQueue: int) → int[]Examples
Example 1
arrivalTimes = [0,0,0,1,1]capacity = 2refillInterval = 2maxQueue = 2return = [0,0,2,4,-1]Two requests consume the initial tokens. The next two wait and run at refills 2 and 4. The last request arrives while the two-slot queue is full.
Example 2
arrivalTimes = [1,10,10,10]capacity = 1refillInterval = 3maxQueue = 1return = [1,10,12,-1]Idle refills restore the token before time 10. At that time one request runs, one waits for time 12, and the third same-time request is dropped.
Example 3
arrivalTimes = [0,1,2,3]capacity = 1refillInterval = 2maxQueue = 0return = [0,-1,2,-1]With no queue, requests without an immediate token are dropped. The refill at time 2 occurs before that time's arrival.
Constraints
0 <= arrivalTimes.length <= 1000000 <= arrivalTimes[i] <= 1000000000arrivalTimesis nondecreasing.1 <= capacity <= 1000001 <= refillInterval <= 100000 <= maxQueue <= 100000- Every returned processing time fits a signed 32-bit integer.