Skip to main content
Problem 25

Build a User Action Rate Limiter

EASYBUILD
Hash Maps & Sets+1

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_actions actions have been recorded for that user in the last window_seconds seconds — and no otherwise. If the action is allowed, record it.

A timestamp that is exactly window_seconds old has just expired and does not count.

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.
Examples
Example 1
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
Note

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.

Example 2
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
Note

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.

Example 3
Input
max_actions=3, window_seconds=60
is_allowed('alice', 0, 3, 60)
is_allowed('alice', 1, 3, 60)
is_allowed('alice', 2, 3, 60)
is_allowed('bob', 0, 3, 60)
Output
True
True
True
True
Note

Alice's limit has no effect on Bob — each user's history is tracked separately.

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.
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?

Hints
Related Practice
Track
Algorithms & Data Structures

Keep moving through related algorithms & data structures problems and build a stronger search-friendly practice loop around this topic.

View track →
Problem 31
Fix the Memory-Leaking LRU Cache
hard
Problem 32
Extract the Smallest Matching Log Window
hard
Problem 33
Split Video Jobs Across Workers
hard
Console output will appear here...