How should I practice Per-Client Sliding-Window Rate Limiter?

Start by reading the full statement, solve the visible examples, then compare the pattern against related Nike, Inc. onsite interview problems in FastPrep.

Is Per-Client Sliding-Window Rate Limiter associated with Nike, Inc.?

FastPrep tags this as a Nike, Inc. onsite interview coding practice problem when the problem catalog has that company and stage context.

Problem · Hash Table

Per-Client Sliding-Window Rate Limiter

Learn this problem

● Medium

Nike, Inc.FULLTIMEONSITE INTERVIEW

Problem statement

Process an ordered batch of requests through a per-client sliding-window rate limiter. Each request i calls allowRequest(clientIds[i], timestamps[i]). A client may have at most limit accepted requests in the trailing windowSeconds seconds.

For a request at time timestamp, keep an earlier accepted request at time acceptedTime in the active window exactly when acceptedTime > timestamp - windowSeconds. Expire older accepted requests before deciding the current request. Accept the request when that client then has fewer than limit active accepted requests; an accepted request enters the window, while a rejected request does not.

Timestamps are globally nondecreasing, and requests at the same timestamp are processed in input order. Remove a client’s stored state as soon as it has no active accepted requests. Return one boolean decision for every request.

Function

allowRequests(clientIds: String[], timestamps: int[], limit: int, windowSeconds: int) → boolean[]

Examples

Example 1

clientIds = ["a","a","a","b","a","a"]timestamps = [0,1,2,2,3,5]limit = 3windowSeconds = 5return = [true,true,true,true,false,true]

Client a fills its window at times 0, 1, and 2, so its request at time 3 is rejected. At time 5, the accepted request at time 0 has expired, so the new request is accepted. Client b is independent.

Example 2

clientIds = ["x","x","x","x"]timestamps = [0,0,3,3]limit = 2windowSeconds = 3return = [true,true,true,true]

The first two same-time requests fill the window. At time 3, both accepted requests from time 0 are exactly at the expiration boundary and leave the window before either new request is processed.

Constraints

1 <= clientIds.length <= 100000.
clientIds.length == timestamps.length.
Each client ID is a nonempty printable ASCII string of length at most 50.
0 <= timestamps[i] <= 10^9.
timestamps is nondecreasing.
1 <= limit <= 100000.
1 <= windowSeconds <= 10^9.