Implement a sliding-window rate limiter allow()

Q: Implement a sliding-window rate limiter allow()

This question evaluates understanding of sliding-window rate limiting, time-windowed counting, and per-user state management for high-throughput services.

Q: How do I approach Coding & Algorithms interview questions?

Coding & Algorithms questions require understanding of core concepts and practice. PracHub provides solutions with explanations to help you master coding & algorithms interviews.

Question

Loading...

Problem

Implement a sliding-window log rate limiter.

Design a class RateLimiter initialized with:

maxRequests (e.g., 100)
windowMillis (e.g., 60_000)

API

Implement:

boolean allow(String userId, long timestampMillis)

Behavior

For each userId independently:

Return true if the number of allowed requests in the time interval (timestampMillis - windowMillis, timestampMillis] is strictly less than maxRequests .
If returning true , record this request as allowed.
Otherwise return false and do not record it.

Constraints

Up to 10^5 calls.
Timestamps are non-decreasing per userId .
Optimize for time and memory (e.g., discard timestamps that fall out of the window).

Implement a sliding-window rate limiter allow()

Quick Overview

Problem

API

Behavior

Constraints

Comments (0)