Questions / Quant development, Trading system components
A token bucket
The bucket refills 1 token per second and holds at most 3. How many requests pass?
def take(rate, burst, times):
tokens, last, ok = burst, 0.0, 0
for t in times:
tokens = min(burst, tokens + (t - last) * rate)
last = t
if tokens >= 1:
tokens -= 1
ok += 1
return ok
print(take(1.0, 3, [0, 0, 0, 0, 0.5, 1.0, 1.0, 3.0, 3.0, 3.0]))Answer it in the app It's free. You get hints, a second try if you miss, and a follow-up question.
Show the answer and worked solution
Answer: 6 requests
- t = 0: three pass, the fourth fails.
- t = 0.5: 0.5 tokens, fails.
- t = 1.0: one passes, the next fails.
- t = 3.0: 2 tokens, two pass.
- Total 6.
Interview shortcut. 3 (burst) + 1 + 2.
Takeaway. A token bucket allows a burst, then the refill rate.
In the app this has a follow-up where one thing about the setup changes. Try the follow-up.