Sliding-Window Rate Limiter
Updated
Problem statement
Implement a keyed rate limiter with a sliding time window. Its two commands have separate roles:
hit key timestamprecords one visit for that key, including visits above the limit.allowed key timestampchecks whether the number of that key's previously recorded visits in the current window is at mostmaxRequests. It returns"true"or"false"and does not record a visit.
At time t, the window is (t - windowSeconds, t]. A recorded hit at t0 counts exactly when t - windowSeconds < t0 <= t. A hit at the left endpoint has expired. Each key has its own history, and repeated hits at the same timestamp each count.
Process the supplied operations in order and return one result for each allowed command, in that same order. An unseen key has zero visits and is allowed. Exactly maxRequests visits is allowed; maxRequests + 1 visits is blocked.
For this exercise, assume operations have valid command syntax and nondecreasing integer timestamps across the entire input. The supplied function is a sequential batch adapter; checking a key is an observation of already recorded hits, rather than a combined permission check and insertion.
Notes
Consider bursts, expiry cleanup, long idle periods, concurrency, and out-of-order timestamps: late timestamps break prefix cleanup, a service can serialize each key's state, and a separate check followed by a hit cannot implement atomic request admission. A fixed window is another acceptable choice; this exercise uses the sliding-window variant.
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 12"]return = ["true", "true", "true", "true"]At time 3, user_1 has two hits. At time 4 it has three, exactly the limit, so both checks are true. At time 12, hits at 1 and 2 have expired and only the hit at 3 remains. The unseen key user_2 has no hits. All timestamps remain nondecreasing.
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", "hit user_1 5", "allowed user_1 5"]return = ["true", "true", "false"]The three checks see two, three, and four hits. Counts at or below three are allowed; four is blocked. All four repeated-timestamp hits are recorded.
Example 3
maxRequests = 1windowSeconds = 3operations = ["hit k 0", "hit k 1", "allowed k 2", "allowed k 3", "allowed k 4", "allowed missing 4"]return = ["false", "true", "true", "true"]At time 2 both hits count and exceed the limit. At time 3 the hit at 0 is exactly at the left boundary and expires; one hit remains. At time 4 the hit at 1 also expires. Checking missing creates no hit.
Constraints
1 <= maxRequests <= 10^4and1 <= windowSeconds <= 10^9.0 <= operations.length <= 10^4; at most1000operations areallowedchecks.- Timestamps are decimal integers from
0through10^12, in nondecreasing order across all operations. - Each operation is
"hit key timestamp"or"allowed key timestamp", with exactly one space between fields. Keys contain 1–32 ASCII letters, digits, underscores, or hyphens. - The active interval is
(t - windowSeconds, t]. Hits exactly at the left endpoint expire. - Every hit is recorded, even when the history already exceeds the limit. Duplicate timestamps count separately, and keys are independent.
allowedreturns"true"exactly when the in-window count is less than or equal tomaxRequests, without recording a hit.- Return only check results in input order. An empty input, or an input with only hits, returns an empty array.
More Stripe Onsite Interview questions
- Render a Task Tree from CSV RowsPHONE SCREEN · ONSITE INTERVIEW · Seen Nov 2026
- Invoice / Payment ReconciliationPHONE SCREEN · ONSITE INTERVIEW · Seen Nov 2026
- Parse Boolean Rule ExpressionsPHONE SCREEN · ONSITE INTERVIEW · Seen Nov 2026
- Transaction Rule Expression EvaluatorONSITE INTERVIEW · Seen Oct 2026
- Evaluate Ordered Action RulesPHONE SCREEN · ONSITE INTERVIEW · Seen Sep 2026
- WebSocket Load Balancer — Parts 1–5OA · ONSITE INTERVIEW · Seen Sep 2026
- Rule-Driven Transaction Fraud DetectionPHONE SCREEN · ONSITE INTERVIEW · Seen Jul 2026
- Account Balance Manager Part 3 - Platform CoverageONSITE INTERVIEW · Seen May 2026
- Account Balance Manager Part 2 - Reject OverdraftsONSITE INTERVIEW · Seen May 2026
- Account Balance Manager Part 1 - Calculate TotalsONSITE INTERVIEW · Seen May 2026
Similar questions at other companies
- Per-Client API Rate LimiterDocker · PHONE SCREEN
- Per-Client Sliding-Window Rate LimiterCVS Health · PHONE SCREEN
- Sliding-Window Rate LimiterAmazon · ONSITE INTERVIEW
- Sliding-Window Rate LimiterUber · PHONE SCREENUber interview questions
- Rate Limiter with Global and Per-User LimitsOpenAI · ONSITE INTERVIEWOpenAI interview questions
- Delayed Streaming Duplicate SuppressionGoogle · PHONE SCREENGoogle interview questions
- Metric Counter with a Fake ClockSnap Inc. · ONSITE INTERVIEWSnap Inc. interview questions
- Per-Client Sliding-Window Rate LimiterNike, Inc. · ONSITE INTERVIEWNike, Inc. interview questions
- Completions API Rate LimiterCursor · PHONE SCREENCursor interview questions
- Key-Value Store GET and PUT QPSDatabricks · PHONE SCREENDatabricks interview questions