Sliding-Window Rate Limiter
Design a rate limiter using a queue, with a rate and a window. Time is passed in explicitly, so nothing here depends on the clock.
Implement SlidingWindowLimiter(limit, window): allow(key, now) admits a request when fewer than limit requests for key were admitted in the window (now - window, now], and records it. Rejected requests are not recorded. Keys are independent.
limiter = SlidingWindowLimiter(2, 10)
limiter.allow("k", 0) -> true
limiter.allow("k", 1) -> true
limiter.allow("k", 2) -> false // two already inside (-8, 2]
limiter.allow("k", 10) -> true // the request at 0 has aged outHints
Hint 1
Keep a queue of admitted timestamps per key. On each call, pop from the front while the oldest timestamp is at or before now − window.
Hint 2
Admit if the queue is shorter than the limit and push now. The structure grows one entry per key — say how you would expire idle keys.