Sliding window rate limiter

Sliding window rate limiter

Problem

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 Date.now() 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.
  }