How should I practice Cached Lazy Token Buckets?

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

Is Cached Lazy Token Buckets associated with xAI?

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

Problem · Hash Table

Cached Lazy Token Buckets

Learn this problem

● Medium

xAIFULLTIMEONSITE INTERVIEW

Problem statement

Process operations in nondecreasing timestamp order.

["CONFIG", user, capacity, refillPerSecond, initialTokens, timestamp] creates that user's cached bucket.
["ALLOW", user, cost, timestamp] lazily refills only that user's bucket, then tries to consume cost tokens.

At an ALLOW timestamp, add (timestamp - lastRefillTimestamp) * refillPerSecond tokens, capped at capacity, and advance the bucket's last-refill timestamp. If at least cost tokens are available, subtract them and return true; otherwise leave the refilled balance unchanged and return false.

Return one lowercase result string for each ALLOW operation.

Function

processTokenBuckets(operations: String[][]) → String[]

Examples

Example 1

operations = [["CONFIG","fast","10","3","4","0"],["ALLOW","fast","5","0"],["ALLOW","fast","4","1"],["ALLOW","fast","8","2"],["ALLOW","fast","2","4"]]return = ["false","true","false","true"]

The first request fails with only 4 tokens. At time 1 the bucket refills to 7 and spends 4; at time 2 it refills to 6, so cost 8 still fails. By time 4 it reaches capacity 10 and cost 2 succeeds.

Example 2

operations = [["CONFIG","fast","10","5","10","0"],["CONFIG","slow","4","1","1","0"],["ALLOW","slow","2","0"],["ALLOW","fast","8","0"],["ALLOW","slow","2","1"],["ALLOW","fast","5","1"]]return = ["false","true","true","true"]

The two users have independent capacities, refill rates, balances, and timestamps. A denied request does not consume the slow user's single token.

Constraints

1 <= operations.length <= 200000.
Each user is configured exactly once before its first ALLOW.
1 <= capacity, cost <= 10^18.
0 <= refillPerSecond, initialTokens <= capacity.
0 <= timestamp <= 10^18, and timestamps are globally nondecreasing.
User names are non-empty ASCII strings.