How should I practice Token Bucket Request Decisions?

Start by reading the full statement, solve the visible examples, then compare the pattern against related Plaid onsite interview problems in FastPrep.

Is Token Bucket Request Decisions associated with Plaid?

FastPrep tags this as a Plaid onsite interview coding practice problem when the problem catalog has that company and stage context.

Problem · Simulation

Token Bucket Request Decisions

Learn this problem

● Medium

PlaidFULLTIMEONSITE INTERVIEW

Problem statement

Simulate a token-bucket rate limiter for requests arriving at integer-second timestamps.

For this exercise, assume the bucket starts full with capacity tokens. Immediately before each request, add refillRate tokens for every whole second elapsed since the previous request, capped at capacity. A request is allowed and consumes one token when a token is available; otherwise it is rejected. Process requests in the supplied nondecreasing order and return one decision per request.

Function

allowRequests(arrivalTimes: int[], capacity: int, refillRate: int) → boolean[]

Examples

Example 1

arrivalTimes = [0,0,0,1]capacity = 2refillRate = 1return = [true,true,false,true]

The first two requests consume the initial tokens. The third is rejected, and one token refills before the request at time 1.

Example 2

arrivalTimes = [1,2,10]capacity = 1refillRate = 1return = [true,true,true]

At least one second separates every pair of requests, so the one-token bucket refills before each request.

Constraints

1 <= arrivalTimes.length <= 10^5
0 <= arrivalTimes[i] <= 10^9
arrivalTimes is nondecreasing.
1 <= capacity, refillRate <= 10^6