255. Token Bucket Resource Allocation

Token Bucket Resource Allocation

You are given a token bucket with a fixed number of tokens. Users can request tokens from the bucket. A request is granted only when enough tokens are currently available.

When a request is granted, that user holds those tokens for exactly 1 hour. After 1 hour, the tokens expire automatically and return to the bucket.

A user may also manually release all currently active tokens held by them before expiry. Expired tokens must be cleaned up before processing every method call.

Class

TokenBucketResourceAllocation

Constructor

TokenBucketResourceAllocation(int capacity)

capacity is the maximum number of tokens in the bucket.
Initially, all capacity tokens are available.

Methods

Request Tokens

String requestTokens(String userId, int tokens, long currentTimeMs)

Before processing the request, all expired token grants must be returned to the bucket.
If tokens tokens are available, grant the request and return "GRANTED".
If fewer than tokens tokens are available, reject the request and return "REJECTED".
Each granted request expires exactly after 3,600,000 milliseconds from currentTimeMs.
The same user may have multiple active grants.

Release Tokens

String releaseTokens(String userId, long currentTimeMs)

Before releasing, all expired token grants must be returned to the bucket.
Release all active, non-expired tokens currently held by userId.
If at least one token is released, return "RELEASED".
If the user has no active tokens, return "NO_ACTIVE_TOKENS".

Get Available Tokens

int getAvailableTokens(long currentTimeMs)

Before returning the answer, all expired token grants must be returned to the bucket.
Return the number of currently available tokens.

Rules

All expired grants are processed before every method call.
A grant created at time t expires when currentTimeMs >= t + 3,600,000.
If multiple grants expire at the same time, they may be processed in any order because the final available token count is the same.
Manual release removes only active grants. Already expired grants are cleaned up first and are not considered manually released.

Constraints

1 ≤ capacity ≤ 1,000,000
1 ≤ tokens ≤ 1,000,000
1 ≤ userId.length() ≤ 100
0 ≤ currentTimeMs ≤ 1,000,000,000,000
currentTimeMs is non-decreasing across all method calls.

Examples

Example 1

TokenBucketResourceAllocation(capacity = 5)

Initializes a bucket with 5 available tokens.

requestTokens(userId = "alice", tokens = 3, currentTimeMs = 1000)

Output: "GRANTED"

Alice receives 3 tokens, so 2 tokens remain available.

requestTokens(userId = "bob", tokens = 3, currentTimeMs = 2000)

Output: "REJECTED"

Only 2 tokens are available, so Bob's request is rejected.

getAvailableTokens(currentTimeMs = 3000)

Output: 2

Example 2

TokenBucketResourceAllocation(capacity = 4)

requestTokens(userId = "u1", tokens = 4, currentTimeMs = 5000)

Output: "GRANTED"

getAvailableTokens(currentTimeMs = 3604999)

Output: 0

The grant has not expired yet because only 3,599,999 milliseconds have passed.

getAvailableTokens(currentTimeMs = 3605000)

Output: 4

The grant has now expired exactly after 3,600,000 milliseconds.

Example 3

TokenBucketResourceAllocation(capacity = 6)

requestTokens(userId = "sam", tokens = 2, currentTimeMs = 10)

Output: "GRANTED"

requestTokens(userId = "sam", tokens = 3, currentTimeMs = 20)

Output: "GRANTED"

releaseTokens(userId = "sam", currentTimeMs = 30)

Output: "RELEASED"

Sam's two active grants are manually released, returning 5 tokens.

getAvailableTokens(currentTimeMs = 40)

Output: 6