Rate Limiter

Implement rateLimiter(timestamps, windowMs, maxRequests). You're given a chronologically-sorted array of past request timestamps (milliseconds, ascending), a sliding window size, and a per-window cap. Return the subset of timestamps that would have been allowed through — the rest were rejected for blowing the quota.

The rule is the sliding-window version of rate limiting: for each timestamp t, count how many of the previously-allowed timestamps fall within (t - windowMs, t]. If that count is less than maxRequests, allow t. Otherwise reject it. Crucially, the count is over allowed-only history — rejected requests do not consume the quota of later windows.

Signature

// timestamps: number[]  — sorted ascending, ms since epoch
// windowMs:   number    — sliding window size in ms
// maxRequests: number   — max allowed per window
// returns:    number[]  — the subset of timestamps that were ALLOWED,
//                         in the same order as input
function rateLimiter(timestamps: number[], windowMs: number, maxRequests: number): number[];

Examples

// Three per second, all bursting in 600ms — first 3 allowed, rest rejected.
rateLimiter([100, 200, 300, 400, 500, 600], 1000, 3);
// → [100, 200, 300]

// Spread far apart — every request fits its own window.
rateLimiter([0, 2000, 4000, 6000], 1000, 2);
// → [0, 2000, 4000, 6000]

// Tied timestamps — the first `max` of the tie are allowed; later ones rejected.
rateLimiter([100, 100, 100, 100], 1000, 2);
// → [100, 100]

Notes

• Allowed-only counting. A rejected timestamp does not count toward later windows. Only timestamps you previously allowed consume the quota. This is what makes it a true rate limiter and not just a moving filter.
• Window is left-open, right-closed. The window for timestamp t is (t - windowMs, t]. A previously-allowed timestamp exactly equal to t - windowMs is out of the window. Pick a side, document it — we picked left-exclusive because it matches how most rate-limit systems treat "now minus window" as already aged-out.
• Sorted input is contract. The caller guarantees timestamps is ascending. If it isn't, behavior is undefined — don't sort defensively, that hides bugs at the caller.
• Tied timestamps are valid. Two requests with the same ms are both in every window that contains that ms. The first maxRequests of the tie are allowed; the rest rejected.
• Output preserves input order. The result is a subset of timestamps in the same order — never reordered, never reshuffled.
• Don't worry about real-clock pacing, async, or distributed coordination. This is a pure synchronous function over an array of numbers.