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.

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
Console output will appear here...