How should I practice Concurrent Token-Bucket Rate Limiter?

Start by reading the full statement, solve the visible examples, then compare the pattern against related Charta Health phone screen problems in FastPrep.

Is Concurrent Token-Bucket Rate Limiter associated with Charta Health?

FastPrep tags this as a Charta Health phone screen coding practice problem when the problem catalog has that company and stage context.

Problem · Concurrency

Concurrent Token-Bucket Rate Limiter

Learn this problem

● Medium

Charta HealthFULLTIMEPHONE SCREEN

Problem statement

Simulate a token-bucket rate limiter. The bucket has integer capacity, starts full at timestamp 0, and refills continuously at refillPerSecond tokens per second.

Process the acquire operations in input order. Operation i occurs at timestamps[i] milliseconds and requests requestedTokens[i] whole tokens. Before deciding that operation, refill the bucket through its timestamp and cap the available amount at capacity. If enough tokens are available, consume the entire request and return true; otherwise consume nothing and return false.

Fractional tokens are retained exactly between operations and are never rounded. Operations with the same timestamp represent an atomic linearization of concurrent callers and are processed in input order. Return one Boolean result per operation.

Function

applyTokenBucket(capacity: int, refillPerSecond: int, timestamps: int[], requestedTokens: int[]) → boolean[]

Examples

Example 1

capacity = 3refillPerSecond = 2timestamps = [0,0,250,500,1000]requestedTokens = [3,1,1,1,2]return = [true,false,false,true,false]

The first request empties the bucket. At 250 ms only half a token exists, while at 500 ms one full token exists. The final request sees only one token and is rejected.

Example 2

capacity = 5refillPerSecond = 1timestamps = [0,2000,2000,7000]requestedTokens = [4,3,1,5]return = [true,true,false,true]

After two seconds the bucket has exactly three tokens. The next same-time request is rejected without changing the balance, and the long idle period fills the bucket to capacity.

Example 3

capacity = 1000000refillPerSecond = 1000000timestamps = [0,1000000000]requestedTokens = [1000000,1000000]return = [true,true]

The first request empties the bucket. The second operation occurs after a long idle period, so the bucket is capped back at capacity. Wide integer arithmetic is required for the refill product.

Constraints

1 <= timestamps.length == requestedTokens.length <= 5000.
1 <= capacity, refillPerSecond <= 10^6.
0 <= timestamps[i] <= 10^9, and timestamps are nondecreasing.
1 <= requestedTokens[i] <= capacity.
Each listed operation is one atomic acquire decision in the given order.