Rate LimiterStep 2 of 5

Sliding-Window Log

12345

Step 2 — Sliding-Window Log

Fixed windows let a burst straddle the boundary. The sliding-window log fixes that exactly: remember the timestamp of every request, and on each new request, drop timestamps older than window seconds and allow only if fewer than limit remain.

Implement:

  • allow() — evict timestamps at or before now - window, then allow (and record now) if fewer than limit are left

It's precise, but the cost is memory: you store one timestamp per request in the window. A deque makes the eviction from the front cheap.

Hints
Starter code
import time
from collections import deque


class SlidingWindowLog:
    def __init__(self, limit, window, clock=time.time):
        self.limit = limit
        self.window = window
        self.clock = clock
        self._timestamps = deque()

    def allow(self):
        """Evict expired timestamps, then allow if under the limit."""
        # TODO:
        #   now = self.clock()
        #   while self._timestamps and self._timestamps[0] <= now - self.window:
        #       self._timestamps.popleft()
        #   if len(self._timestamps) < self.limit:
        #       append now and return True
        #   return False
        pass
Write it on a laptop

The editor and the test runner need a wide screen. Open this page on a desktop browser and your progress will be waiting.

PreviousNext step