In-Memory Rate Limiter

Question

#In-Memory Rate Limiter

## Problem
Implement a thread-safe in-memory `RateLimiter` that decides whether a request for a given key should be allowed.

You must implement:

- `allow(key: str, now_ms: int) -> bool`

This method is called for every request and returns whether the request is allowed at time `now_ms`.

## Policy
The interviewer may ask you to implement **one** of the following policies:

### Option A — Fixed Window
Allow at most `limit` requests per `window_ms`.

Example:
- `limit = 3`
- `window_ms = 1000`

For a given key, at most 3 requests may be allowed in each window of length 1000 ms.

### Option B — Sliding Window
Allow at most `limit` requests in the most recent `window_ms`.

This is stricter than fixed window because it avoids boundary spikes.

### Option C — Token Bucket
Maintain a bucket with:
- `capacity = limit`
- refill rate = `limit / window_ms` tokens per ms

Each request consumes 1 token.
A request is allowed only if at least 1 token is available.

## Constraints
- Must support many keys, such as user IDs or IPs
- Must be thread-safe
- Should discuss how to evict or clean up idle keys
- Scale assumptions:
  - up to `1e6` calls
  - up to `1e5` keys

## E

Accepted Answer

A detailed reference solution is available to Crack ML Interview members.