Problem
You are implementing a per-user rate limiter. Time is discretized into integer time buckets (e.g., each bucket is 1 second).
You are given two parameters:
-
x
: window size in buckets
-
y
: maximum allowed requests within any trailing window of
x
buckets
Implement:
boolean shouldPass(int timeBucket)
Each call represents an incoming request attempt at the given timeBucket. The function returns:
-
true
if the request is allowed
-
false
if the request should be rate-limited
Rate-limit rule
A request at time t should be allowed iff the number of request attempts whose bucket is in:
[t - x + 1, t] (inclusive)
is < y (i.e., the current request would not make it exceed y).
Assumption: Even rejected attempts still count toward the limit (they are still request attempts).
Notes / Constraints
-
timeBucket
values are non-decreasing across calls.
-
Aim for efficient time and space usage as the number of requests grows.
-
Provide a few test cases (including edge cases such as repeated calls in the same bucket, large gaps between buckets, and bursts).