Implement a sliding-window rate limiter

Q: Implement a sliding-window rate limiter

This question evaluates a candidate's ability to implement a sliding-window rate limiter, emphasizing time-based algorithms, per-key state management, and efficient data-structure choices to achieve near-O(1) operations.

Q: How do I approach Coding & Algorithms interview questions?

Coding & Algorithms questions require understanding of core concepts and practice. PracHub provides solutions with explanations to help you master coding & algorithms interviews.

Question

Problem

Design and implement an in-memory rate limiter using a sliding time window.

You are given a stream of requests. Each request has:

key (e.g., user ID, API token, or IP)
timestamp (integer seconds, non-decreasing for a given key )

Implement an API:

bool allow(key, timestamp)

The limiter should allow at most N requests per W seconds for each key.

Requirements

If a request is allowed, it counts toward the limit.
Sliding window means the window is (timestamp - W, timestamp] (or clearly define inclusivity and keep it consistent).
Support many distinct keys.

Example

If N = 3, W = 10 seconds:

Requests for the same key at times [1, 2, 3] are allowed.
A request at time 4 is denied (already 3 in last 10 seconds).
A request at time 12 may be allowed depending on the sliding window definition (e.g., requests at time 1 may have expired).

Constraints (assumptions you may use)

Timestamps fit in 64-bit integer.
Aim for near O(1) average time per allow call.
Memory should not grow unbounded for inactive keys (you may describe a cleanup strategy).

Implement a sliding-window rate limiter

Overview

Problem

Requirements

Example

Constraints (assumptions you may use)

Comments (0)