Token-Bucket Rate Limiter

HardSystem Design

Description

Design a **token-bucket rate limiter**: a structure that allows up to `capacity` requests at once and refills tokens at a steady rate of `refillRate` tokens per second. The bucket starts full at time `0` (i.e. `capacity` tokens). Each `allow(timestamp)` call: 1. Refills the bucket based on the elapsed seconds since the last refill: `tokens = min(capacity, tokens + (timestamp - lastRefill) * refillRate)`. Fractional tokens are allowed. 2. If `tokens >= 1`, deduct `1` and return `true` (allow). 3. Else return `false` (reject). Timestamps are non-decreasing. `refillRate` and `capacity` may be floats. **For the auto-grader:** implement `tokenBucketOps(capacity, refillRate, requests)` where each request is a timestamp (in seconds). Return an array of booleans matching the result of each `allow()`.

Example 1

Input: capacity = 3, refillRate = 1, requests = [0,0,0,0,2]

Output: [true,true,true,false,true]

Explanation: At t=0 the bucket is full (3 tokens). The first three calls each consume one token (bucket → 2, 1, 0). The fourth call at t=0 finds 0 tokens → reject. At t=2, two seconds have passed so 2 tokens refilled (capped to capacity); one is consumed → allow.

Example 2

Input: capacity = 2, refillRate = 0.5, requests = [0,0,1,2,4]

Output: [true,true,false,false,true]

Explanation: Capacity 2 is exhausted by the first two calls. At t=1, only 0.5 tokens have refilled (< 1) → reject. At t=2, total refilled = 1.0 → still need to wait (we already rejected at t=1 - the rejection consumes nothing, so at t=2 we have 1.0 token; integer? 1.0 >= 1 → allow!). Re-walk: at t=2, tokens = 0 + 2*0.5 = 1.0 → allow, bucket → 0. At t=4, tokens = 0 + 2*0.5 = 1.0 → allow.

Constraints

- 0 < capacity <= 10^6 - 0 < refillRate <= 10^6 - 0 <= requests.length <= 10^5 - Timestamps are non-decreasing non-negative numbers up to 10^9.

Loading editor...