How should I practice In-Memory Fixed-Window Rate Limiter?

Start by reading the full statement, solve the visible examples, then compare the pattern against related Rippling phone screen problems in FastPrep.

Is In-Memory Fixed-Window Rate Limiter associated with Rippling?

FastPrep tags this as a Rippling phone screen coding practice problem when the problem catalog has that company and stage context.

In-Memory Fixed-Window Rate Limiter

Rippling● EasyFULLTIMEPHONE SCREEN

Learn

Problem statement

Process a batch of requests through an in-memory, per-client rate limiter. Request i belongs to clientIds[i] and arrives at timestamps[i] seconds.

Use a fixed-window policy. Time is divided into half-open windows of length windowSeconds, aligned to timestamp 0. Therefore, timestamp t belongs to window [floor(t / windowSeconds) * windowSeconds, (floor(t / windowSeconds) + 1) * windowSeconds).

Each client has an independent quota in each window:

Allow a request when fewer than maxRequests requests for that client have already been allowed in the same window.
An allowed request consumes one quota slot.
A rejected request does not change the limiter state.

The timestamps are nondecreasing. Requests with the same timestamp are processed in input order. Return one boolean decision for every request in the original order.

Function

applyRateLimit(clientIds: String[], timestamps: int[], maxRequests: int, windowSeconds: int) → boolean[]

Examples

Example 1

clientIds = ["alice","alice","bob","alice","alice","alice"]timestamps = [1,2,3,9,10,10]maxRequests = 2windowSeconds = 10return = [true,true,true,false,true,true]

Alice fills her two slots in window [0, 10) at timestamps 1 and 2, so her request at 9 is rejected. Bob has an independent quota. Timestamp 10 begins a new window, so both later Alice requests are allowed.

Example 2

clientIds = ["x","x","y","x","x"]timestamps = [0,4,4,5,5]maxRequests = 1windowSeconds = 5return = [true,false,true,true,false]

Client x can use one slot in [0, 5) and one new slot in [5, 10). Client y is unaffected by x's quota.

Example 3

clientIds = ["a","b","a","b","a","b"]timestamps = [7,7,7,7,7,7]maxRequests = 2windowSeconds = 3return = [true,true,true,true,false,false]

All requests share one timestamp and are processed in input order. Each client independently allows its first two requests and rejects its third.

Constraints

1 <= clientIds.length == timestamps.length <= 2 * 10^5.
Each clientIds[i] is a nonempty printable ASCII string of length at most 50.
0 <= timestamps[i] <= 10^9, and timestamps is nondecreasing.
1 <= maxRequests <= 10^5.
1 <= windowSeconds <= 10^9.