← Gym/Rate Limiter
00:00/ 20 min

🧭 Do not search for the first 15 minutes. When stuck: re-read the requirements → define I/O → choose the data structure → trace a small example by hand → write code.

Implement a RateLimiter that caps each user's request rate in front of an API gateway.

Shared rules

Requests arrive one at a time as (user id, timestamp) pairs. The limiter judges each one allowed (True) or denied (False).

  • window is an integer number of seconds; limit is the maximum number of requests permitted inside that window.
  • A request at timestamp t is allowed only when fewer than limit already allowed requests sit inside the closed interval [t - window, t].
  • Denied requests are not recorded. Repeated denials therefore never push the window forward.
  • Each user's window and counters are fully independent.
  • Timestamps are non-decreasing (the same value may repeat).
  • Requests sharing a timestamp each count separately.

Example

python
r = RateLimiter(limit=2, window=3)

r.allow("A", 1)   # True   — 0 allowed requests in the window [-2, 1]
r.allow("A", 2)   # True   — 1 in the window [-1, 2]
r.allow("B", 3)   # True   — B is independent of A
r.allow("A", 4)   # False  — the window [1, 4] holds A's requests at 1 and 2 → at the limit
r.allow("A", 6)   # True   — the window [3, 6] no longer contains 1 or 2

Watch the boundary: the window includes both ends. With window=3, the window at t=4 covers the four moments 1, 2, 3, 4.

Level structure

LevelAdded requirement
1allow — the basic decision and per-user independence
2count, reset — reading current window usage and clearing history
3set_limit — per-user limit overrides
4stats — overall and per-user allow/deny counters

Each level must preserve the behavior of the previous ones. Submitting re-runs the earlier levels' tests, so breaking old behavior while adding a feature shows up immediately.

Level 1 · The basic decision

Implement the RateLimiter class.

python
RateLimiter(limit: int, window: int)
allow(user_id: str, timestamp: int) -> bool
  • allow returns True when the request is permitted and False when denied.
  • The decision rule matches the shared spec — allow when the closed window [t - window, t] holds fewer than limit allowed requests.
  • Windows and counters are independent per user.
  • With limit of 0, nothing is ever allowed.