A sliding window log rate limiter records the exact timestamps of recently allowed requests. It avoids the boundary burst of fixed-window counters by evaluating a trailing window for every request.
Design a SlidingWindowLogRateLimiter class:
SlidingWindowLogRateLimiter(int limit, int windowSeconds) creates an empty limiter.boolean allow(int timestamp) processes one request and returns whether it is allowed.
Timestamps passed to one object are non-decreasing. For a request at time t, an earlier allowed request counts only when its timestamp is strictly greater than t - windowSeconds.
Remove timestamps outside that range. If fewer than limit allowed requests remain, record t and return true. Otherwise, return false without recording the denied request.
Example 1:
Input:
Output:
Explanation: Requests at 1 and 2 fill the limit. Both timestamps remain in the trailing window at times 3 and 4, so those requests are denied.
Example 2:
Input:
Output:
Explanation: At time 11, timestamp 1 is exactly windowSeconds old and no longer counts. The same boundary rule removes 11 at time 21.
Constraints
1 <= limit <= 10^51 <= windowSeconds <= 10^90 <= timestamp <= 2^31 - 1- Timestamps passed to one object are non-decreasing.
- At most
10^5 calls are made to allow. - Only allowed requests count toward the limit.
Design a Sliding Window Log Rate Limitermedium