FastPrepBounded Token-Bucket Request Queue
Problems/Bounded Token-Bucket Request Queue

Bounded Token-Bucket Request Queue

Plaid logoPlaid● MediumFULLTIMEONSITE INTERVIEW
QuestionFunctionExamplesConstraints

Problem statement

Source note: The source reports a classic rate limiter, then asks about a bucket-backed queue, memory overflow, and throughput. It omits the exact timing and output rules, which are bounded here as a conventional deterministic token-bucket simulation. The judged core task matches the visible source at about 72%.

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 <= 100000
  • 0 <= arrivalTimes[i] <= 1000000000
  • arrivalTimes is nondecreasing.
  • 1 <= capacity <= 100000
  • 1 <= refillInterval <= 10000
  • 0 <= maxQueue <= 100000
  • Every returned processing time fits a signed 32-bit integer.

More Plaid problems

  • Validate and Resolve Evaluation ChainsPHONE SCREEN · ONSITE INTERVIEW · Seen Oct 2026
  • Total Pipeline Completion TimePHONE SCREEN · Seen Sep 2026
  • Rule References: Validity and EligibilityPHONE SCREEN · Seen Aug 2026
All Plaid interview questionsSee Plaid hiring insights
Saved
class Solution {
    public int[] scheduleRateLimitedRequests(int[] arrivalTimes, int capacity, int refillInterval, int maxQueue) {
      // write your code here
    }
}
Checking account…