Skip to content
RED SAGSkills
medium30 ptssimulationdevops

Token Bucket Rate Limiter

An API gateway protects a backend with a token bucket. The bucket holds at most capacity tokens and is full at time 0. A new token is added at every multiple of refillIntervalMs (at refillIntervalMs, 2 * refillIntervalMs, ...); a token added while the bucket is full is lost.

Requests arrive at the times in timestamps (milliseconds, non-decreasing). A request is allowed if a token is available, and consumes it; otherwise it is rejected. A refill that happens at exactly the same millisecond as a request is applied before the request.

Return an array of booleans, one per request.

Example 1

Input: capacity = 2, refillIntervalMs = 1000, timestamps = [0,100,200,1000,1500,2500,5000]
Output: [true,true,false,true,false,true,true]
Explanation: Two tokens are spent at once; refills arrive at 1000 and 2000; three ticks by 5000 refill the bucket to the cap.

Example 2

Input: capacity = 1, refillIntervalMs = 100, timestamps = [0,99,100,150,200]
Output: [true,false,true,false,true]

Constraints

  • 1 <= capacity <= 10^4
  • 1 <= refillIntervalMs <= 10^6
  • 0 <= timestamps.length <= 10^5
  • 0 <= timestamps[i] <= 10^12
Hint 1

The number of refill ticks in (prev, t] is floor(t / interval) - floor(prev / interval).

Hint 2

Cap at capacity after adding the ticks.

Discussion 0

Join free to post in the discussion.

Good practice for: Backend Developer, Site Reliability Engineer, Cloud Engineer, DevOps Engineer, Full Stack Developer, Mobile App Developer

Run checks your code on 3 sample tests. Submit runs all 7 tests, including hidden ones, and earns points. Use console.log to debug. Python's first run can take a few seconds while it starts.