← All challenges

Sliding window rate limiter

Medium

Allow at most N requests per W seconds per key, sliding window.

Sliding window rate limiter

Problem

Rate limiters protect backends from abuse — API scraping, runaway retries, and accidental hotspots — by bounding how many requests a client may make in a time span. A fixed window (say, 100 requests per minute, resetting on the minute) is cheap but lets a client double its rate by straddling the reset boundary. A sliding window counts only the requests that fall inside the last W milliseconds, so the limit holds at every instant. The tradeoff: you must remember each request's timestamp and drop it once it ages out of the window, instead of resetting a counter.

Implement a sliding-window rate limiter. For each request key, allow at most N requests within a W-millisecond sliding window. The window slides with each request — it is not a fixed tumbling window. Return true if the request is allowed, false if it should be rejected.

Input

  • key: string — The identifier for the client or resource being rate-limited (e.g. IP address, user ID, API key).
  • limit: number — Maximum number of requests allowed within the window. Defaults to 5.
  • windowMs: number — Sliding window size in milliseconds. Defaults to 10,000 (10 seconds).

Output

  • boolean — true if the request is within the rate limit and is allowed; false if it exceeds the limit and should be rejected.

Examples

Example 1:

// 5 requests allowed per 10s window allow('alice'); // true (1st) allow('alice'); // true (2nd) allow('alice'); // true (3rd) allow('alice'); // true (4th) allow('alice'); // true (5th) allow('alice'); // false (6th — over limit)

Output: false

The first 5 calls succeed; the 6th is rejected because the window still contains 5 recent timestamps.

Example 2:

// Different keys are independent for (let i = 0; i < 5; i++) allow('alice'); allow('bob'); // true — bob has a separate window

Output: true

Rate limiting is per-key. Saturating one key does not affect another.

Constraints

  • The window is sliding, not tumbling — rejected requests do not consume quota.
  • Timestamps within the window are tracked per key.
  • Each timestamp is added once and removed once over its lifetime (amortized O(1)).
  • The function uses the provided millisecond clock for timestamps.

Complexity

  • Time: O(1) amortized per call
  • Space: O(K * L) where K is the number of distinct active keys and L is the limit

Starter

export function allow(key: string, limit = 5, windowMs = 10_000): boolean {
    // Track per-key request timestamps in a sliding window; allow when
    // fewer than limit requests fall inside the window, otherwise reject.
  }

API available to your solution

The platform provides a deterministic millisecond clock; use it for all time math instead of reading the system clock. The tests pin the clock to specific values, so your results are reproducible.

long long nowMs();   // current time in milliseconds

Time.nowMs();        // static long nowMs() — current time in milliseconds

func nowMs() int64   // current time in milliseconds

now_ms() -> int      // current time in milliseconds

Date.now()           // fixed to deterministic values by the test runner

Don't declare the clock yourself — it is supplied in every language.

Hints

Answer