Skip to main content
ELYTE
MediumAlgorithms & Data StructuresBuild

In-Memory Rate Limiter

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

Start problemBrowse all problems

What you will practice

PythonHash Maps & SetsAsync PatternsHash MapSliding WindowQueue

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.

Starter files

main.pyEditable starter

What the judge checks

  • Runs in the python environment with the python-function runner.
  • Uses a 2000ms judge budget.
  • Behavior rules include: Only Allowed Requests Count, Per User Independent, Timestamps Non Decreasing Per User.

Constraints

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

Example behavior

Input
requests = [("a", 1), ("a", 2), ("a", 3), ("a", 4)]
limit = 2
window_seconds = 3
Output
[True, True, False, True]

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.

Follow-up

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