Step 3 — Sliding-Window Counter

Storing every timestamp is expensive. The sliding-window counter approximates the log with just two numbers: the count in the current fixed window and the count in the previous one. It weights the previous window by how much of it still overlaps the trailing window.

If elapsed is how far you are into the current window, the estimate is:

weight   = (window - elapsed) / window
estimate = previous_count * weight + current_count

Allow the request if estimate < limit. Keep the two counters correct as windows advance: moving to the very next window shifts current → previous; skipping further ahead means both reset to zero.

Hints

import time class SlidingWindowCounter: def __init__(self, limit, window, clock=time.time): self.limit = limit self.window = window self.clock = clock self._index = None # current window index self._current = 0 self._previous = 0 def _roll(self, index): """Advance internal counters to the given window index.""" if self._index is None or index >= self._index + 2: self._previous = 0 self._current = 0 elif index == self._index + 1: self._previous = self._current self._current = 0 self._index = index def allow(self): """Allow if the weighted estimate of recent requests is under the limit.""" # TODO: # now = self.clock() # index = int(now // self.window) # self._roll(index) # elapsed = now - index * self.window # weight = (self.window - elapsed) / self.window # estimate = self._previous * weight + self._current # if estimate < self.limit: count it (self._current += 1) and return True # return False pass

Step 3 — Sliding-Window Counter

If elapsed is how far you are into the current window, the estimate is:

weight = (window - elapsed) / window estimate = previous_count * weight + current_count

Allow the request if estimate < limit. Keep the two counters correct as windows advance: moving to the very next window shifts current → previous; skipping further ahead means both reset to zero.

Hints