Questions / Quant development, Trading system components
A sliding-window limiter
At most 3 requests per 10-second window. How many are allowed?
from collections import deque
class Window:
def __init__(self, limit, span):
self.limit, self.span, self.q = limit, span, deque()
def allow(self, t):
while self.q and self.q[0] <= t - self.span:
self.q.popleft()
if len(self.q) < self.limit:
self.q.append(t)
return True
return False
w = Window(3, 10)
print(sum(w.allow(t) for t in [0, 1, 2, 5, 10, 11, 12, 13]))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
- 0, 1, 2 pass; 5 fails.
- At 10, 0 expires (0 ≤ 0): pass. At 11, 1 expires: pass. At 12, 2 expires: pass.
- At 13, 10 is still in the window: fail.
Interview shortcut. Three at once, then one per expiry: 3 + 3.
Takeaway. Sliding windows release capacity one request at a time.
In the app this has a follow-up where one thing about the setup changes. Try the follow-up.