How should I practice Sliding-Window Rate Limiter?

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

Is Sliding-Window Rate Limiter associated with Stripe?

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

Problem · Hash Table

Sliding-Window Rate Limiter

Learn this problem

● Medium

StripeFULLTIMEONSITE INTERVIEW

See Stripe hiring insights

Problem statement

Build a rate limiter that tracks API requests per client key and decides whether a client may make a request, using a sliding time window.

The limiter is configured with maxRequests and windowSeconds: a client is allowed only if it has made fewer than maxRequests recorded requests within the most recent windowSeconds. There are two operations:

hit key timestamp — record a request for key at integer time timestamp.
allowed key timestamp — return whether key is currently allowed at timestamp, i.e. whether the number of that key's recorded hits still inside the window is strictly less than maxRequests. This check counts only previously recorded hits; it does not itself record a hit.

A hit at time t0 is inside the window evaluated at time t when t0 > t - windowSeconds (older hits, with t0 <= t - windowSeconds, have expired and must be ignored / cleaned up). Each key is tracked independently; an unseen key has no hits. Hits may share a timestamp, and operations are supplied in nondecreasing timestamp order.

You are given the operations as a String[] in order. Process them and return a String[] containing the result of every allowed operation, in order, as "true" or "false".

Function

runRateLimiter(maxRequests: int, windowSeconds: int, operations: String[]) → String[]

Examples

Example 1

maxRequests = 3windowSeconds = 10operations = ["hit user_1 1", "hit user_1 2", "allowed user_1 3", "hit user_1 3", "allowed user_1 4", "allowed user_1 12", "allowed user_2 5"]return = ["true", "false", "true", "true"]

hit user_1 1, hit user_1 2. allowed user_1 3: window keeps t0 > 3-10, both hits count, 2 < 3 -> true. hit user_1 3: user_1 now has 3 hits. allowed user_1 4: 3 hits in window, 3 < 3 is false -> false. allowed user_1 12: window start = 12-10 = 2, so hits at 1 and 2 expire (t0 <= 2), only the hit at 3 remains, 1 < 3 -> true. allowed user_2 5: new key, 0 hits -> true. Four allowed ops -> four results.

Example 2

maxRequests = 3windowSeconds = 10operations = ["hit user_1 5", "hit user_1 5", "allowed user_1 5", "hit user_1 5", "allowed user_1 5"]return = ["true", "false"]

Burst traffic at the same timestamp. After two hits at t=5, allowed at 5 sees 2 < 3 -> true. A third hit at t=5 makes 3 hits, so allowed at 5 sees 3 < 3 is false -> false. Duplicate timestamps are each counted.

Constraints

Operations are "hit key timestamp" or "allowed key timestamp" with integer timestamps.
A hit at t0 counts at evaluation time t iff t0 > t - windowSeconds.
allowed returns true iff the key's in-window hit count is strictly less than maxRequests; it does not record a hit.
Each key is tracked independently; bursts at the same timestamp are allowed, and operations are in nondecreasing timestamp order.
Return one "true"/"false" per allowed operation, in order.