Skip to main content
ELYTE
EasyAlgorithms & Data StructuresBuild

Build a User Action Rate Limiter

Implement a `RateLimiter` class that tracks how many actions each user has taken within a sliding time window. Each call to `is_allowed` asks: should this user's action go through? The answer is yes if fewer than `max_a...

Start problemBrowse all problems

What you will practice

PythonHash Maps & SetsRate Limiting

Requirements

  • Implement a `RateLimiter` class in `main.py`.
  • `RateLimiter` must have an `is_allowed(self, user_id, timestamp, max_actions, window_seconds)` method that returns `True` or `False`.
  • Return `True` (and record the action) if the user has taken fewer than `max_actions` actions in the half-open window `[timestamp - window_seconds, timestamp)`.
  • Return `False` (and do not record the action) if the user is at or over the limit.
  • Each user has their own independent action history — one user being rate-limited must not affect another.
  • The first action by any user must always be allowed.

Starter files

main.pyEditable starter

What the judge checks

  • Runs in the python environment with the python-pytest runner.
  • Uses a 5000ms judge budget.
  • Behavior rules include: First Action Always Allowed, Actions Within Window Capped, Actions Outside Window Recovered, Separate Users Independent.

Constraints

  • Timestamps are non-negative integers (Unix seconds). They will be passed in non-decreasing order within a single test.
  • Do not use any external libraries — a plain Python `dict` is all you need.
  • `max_actions` and `window_seconds` may differ between calls — handle them dynamically, not by hardcoding.

Example behavior

Input
max_actions=2, window_seconds=10
is_allowed('alice', 0, 2, 10)
is_allowed('alice', 5, 2, 10)
is_allowed('alice', 8, 2, 10)
Output
True
True
False

At t=8, both t=0 and t=5 are within the 10-second window (8-0=8 < 10, 8-5=3 < 10). Alice already has 2 recorded actions — she's at the limit.

Input
max_actions=2, window_seconds=10
is_allowed('alice', 0, 2, 10)
is_allowed('alice', 5, 2, 10)
is_allowed('alice', 10, 2, 10)
Output
True
True
True

At t=10, the t=0 action is exactly 10 seconds old (10-0=10), so it has expired and is no longer in the window. Only t=5 remains — Alice is below the limit.

Follow-up

This implementation stores every timestamp forever. In production, you'd want to prune old entries so memory doesn't grow without bound. Where exactly would you prune, and what data structure would make it fastest?