Map Tile Burst Allowance
A map company sells tile access to app developers. When a user pans the map, the app needs a burst of tiles at once, then nothing for a while. A fixed cap per minute would either block the burst or allow too much in total, so each API key gets a token bucket: it holds up to capacity tokens, a request spends tokens, and one new token drips in every intervalMs milliseconds. A full bucket allows a burst; the drip sets the long-run rate.
This is the token bucket from Rate Limiting, the usual choice for API gateways (see Design a Rate Limiter). No timer refills it: each request works out how many tokens arrived since the last one, which is where most bugs hide.
Your task
Write a class TokenBucket:
constructor(capacity, intervalMs): the bucket starts full at time 0.take(t, cost): a request at timet(milliseconds) that needscosttokens. If the bucket holds at leastcosttokens, remove them and returntrue. Otherwise returnfalseand remove nothing.available(t): return how many tokens the bucket holds at timet, without changing anything else.
Drips happen at fixed times: intervalMs, 2 × intervalMs, 3 × intervalMs, and so on. Each drip adds one token, unless the bucket is already full, in which case that token is lost. A drip at exactly time t counts before the request at t.
class TokenBucket
Examples
new TokenBucket(3, 1000) .take(0, 1) .take(100, 1) .take(200, 1) .take(300, 1) .take(1000, 1) .take(1500, 1) .available(2000)
[null, true, true, true, false, true, false, 1]
The bucket starts with 3 tokens, so the burst at 0, 100 and 200 ms is allowed and empties it. At 300 ms nothing has dripped yet: rejected. The drip at 1,000 ms adds one token, which the request at 1,000 spends. At 1,500 the bucket is empty again. The drip at 2,000 leaves 1 token.
new TokenBucket(2, 1000) .take(0, 2) .take(600, 1) .take(1200, 1) .take(1900, 1) .take(2000, 1)
[null, true, false, true, false, true]
A cost-2 request empties the bucket at 0. At 600 ms no drip has happened. At 1,200 ms the drip at 1,000 has added a token, so the request is allowed. A common bug measures 600 ms "since the last request" at both 600 and 1,200, never reaches 1,000, and wrongly rejects this one. The drip at 2,000 pays for the last request.
Constraints
- 1 ≤ capacity ≤ 1,000,000
- 1 ≤ intervalMs ≤ 1,000,000
- 1 ≤ cost ≤ 1,000,000 (a cost above capacity can never succeed)
- 0 ≤ t ≤ 1,000,000,000,000, and t never decreases from one call to the next
- At most 2,000 calls per test
Start with brute force
A timer that adds one token every interval works on paper, but a gateway with a million API keys cannot run a million timers. Simulating every drip one by one inside each call is also too slow: with a 1 ms interval and calls a trillion milliseconds apart, that is a trillion steps.
Counting drips with one division gives the same result in O(1), and the bucket is just two numbers per key, small enough to keep in a shared in-memory store.
Hints
0 of 4 shown- Hint 1
Between two calls at times
aandb, how many drips happened? Try a = 600, b = 1,200 with a 1,000 ms interval, then a = 0, b = 600. - Hint 2
The number of drips up to time
tisfloor(t / intervalMs). So the drips between two calls are the difference of those two counts, and nothing is lost to rounding. - Hint 3
Store the token count and the drip count at the last update. On every call, add the new drips to the tokens, clamp to
capacity(tokens beyond it are lost), and save the new drip count. - Hint 4
takerefills first, then compares withcost.availablerefills and returns the count; refilling early is harmless because the drip count is stored, not the time of the call.
Walkthrough and solution
Unlocks when you pass every test. Stuck for a while? Looking is fine too, as long as you then close it and write the code yourself.
How to solve it
The bucket is two numbers: tokens now, and how many drips have been counted. Every call first catches up: the drips up to t are floor(t / intervalMs), so the new ones are that minus the stored count.
Trace the second example, capacity 2, interval 1,000:
- t = 0, cost 2: drips 0, nothing new. 2 tokens ≥ 2: take them, 0 left.
- t = 600, cost 1: floor(600 / 1000) = 0 drips, nothing new. 0 < 1: rejected.
- t = 1,200, cost 1: floor(1200 / 1000) = 1, one new drip. 1 token: take it, 0 left, drips stored as 1.
- t = 1,900: still 1 drip, nothing new. Rejected.
- t = 2,000: 2 drips, one new. Allowed.
Storing the drip count, not the time of the last call, is the whole trick. The version that does gained = floor((t - last) / interval); last = t throws away the 600 ms of progress made before the call at 600, so it rejects the request at 1,200. In a real gateway the refill and the take must also happen as one atomic step in the shared store, or two servers can spend the same token.
class TokenBucket {
constructor(capacity, intervalMs) {
this.capacity = capacity;
this.intervalMs = intervalMs;
this.tokens = capacity; // starts full
this.drips = 0; // drips counted so far (drip k happens at k * intervalMs)
}
refill(t) {
const drips = Math.floor(t / this.intervalMs);
// add the drips since the last update; anything above capacity is lost
this.tokens = Math.min(this.capacity, this.tokens + (drips - this.drips));
this.drips = drips;
}
take(t, cost) {
this.refill(t);
if (this.tokens < cost) return false; // not enough: take nothing
this.tokens -= cost;
return true;
}
available(t) {
this.refill(t);
return this.tokens;
}
}class TokenBucket:
def __init__(self, capacity, interval_ms):
self.capacity = capacity
self.interval_ms = interval_ms
self.tokens = capacity # starts full
self.drips = 0 # drips counted so far (drip k happens at k * interval_ms)
def _refill(self, t):
drips = t // self.interval_ms
# add the drips since the last update; anything above capacity is lost
self.tokens = min(self.capacity, self.tokens + (drips - self.drips))
self.drips = drips
def take(self, t, cost):
self._refill(t)
if self.tokens < cost: # not enough: take nothing
return False
self.tokens -= cost
return True
def available(self, t):
self._refill(t)
return self.tokensRun your code to see results here. Run checks the examples. Submit checks every test, including hidden edge cases.