Token Bucket Rate Limiter

You are simulating a token bucket rate limiter.

Parameters:

• capacity: maximum tokens in the bucket.
• refillRate: tokens added per unit time.
• requests: a list of requests with a time and token cost.

Rules:

1. The bucket starts full at time 0.
2. Before each request at time t, refill: tokens = min(capacity, tokens + (t - lastTime) * refillRate)
3. If tokens >= cost, accept the request and deduct cost.
4. Otherwise reject the request.

Return a boolean slice indicating whether each request is accepted.

Types

type Request struct {
    Time int
    Cost int
}

Function signature

func TokenBucketAllow(capacity int, refillRate int, requests []Request) []bool

Example

capacity = 5
refillRate = 1
requests = [
  {Time:0, Cost:4},
  {Time:2, Cost:2},
  {Time:3, Cost:2},
  {Time:3, Cost:1},
]
output = [true, true, true, false]

Constraints

• 0 <= len(requests) <= 100000
• 0 <= capacity, refillRate <= 1_000_000
• 0 <= Time, Cost <= 1_000_000
• Time is non-decreasing in requests

Notes

• If capacity == 0, all positive-cost requests are rejected.
• If Cost == 0, a request is always accepted.