Skip to main content
Problem 2

In-Memory Rate Limiter

MEDIUMBUILD
Hash Map+2

Given a stream of API requests, implement an in-memory rate limiter that decides whether each request should be allowed.

Implement rate_limit(requests, limit, window_seconds) returning a list of booleans. Each request is a pair (userId, timestamp) where timestamp is in seconds. A request is allowed if that userId has fewer than limit allowed requests in the past window_seconds seconds (inclusive). Blocked requests do not count toward the limit.

Requirements
  • Keep the public rate_limit(requests, limit, window_seconds) function signature intact.
  • Return one boolean for each request, preserving the original request order.
  • Track allowed requests independently for each userId.
  • Allow a request only when that user has fewer than limit allowed requests in the inclusive past window_seconds window.
  • Blocked requests must not count toward the limit.
  • Expire old allowed requests as timestamps move outside the active window.
Examples
Example 1
Input
requests = [("a", 1), ("a", 2), ("a", 3), ("a", 4)]
limit = 2
window_seconds = 3
Output
[True, True, False, True]
Note

At t=3, user "a" has 2 allowed requests in [1,3], so it's blocked. At t=4, the window shifts to [2,4] and only t=2 counts, so it's allowed.

Constraints
  • 1 <= len(requests) <= 200000
  • Timestamps for a given userId are non-decreasing
Follow-up

How would you adapt this to a distributed system where requests for the same userId may hit different servers?

Hints
Related Practice
Track
Backend Basics

Keep moving through related backend basics problems and build a stronger search-friendly practice loop around this topic.

View track →
Problem 3
Password Strength Tagger
easy
Problem 5
Config Merge with Deletions
medium
Problem 6
Debounced Search with Stale Response Protection
medium
Console output will appear here...