Also reported as Sliding Window Rate Limiter · Per-Entity Rate Limiter
The round is two graded parts, each with a given signature and its own test cases. Reported follow-ups extend it further (arbitrary fields, per-IP, garbage collection) but those are discussed rather than submitted.
Level 1 — Global Rate Limiter
Implement a rate limiter that processes a sorted list of request timestamps and returns a boolean list indicating whether each request should be allowed or denied.
def rate_limiter(
requestTimestamps: list[int], # sorted list of request timestamps
windowLength: int, # length of the sliding time window
maxRequests: int # max requests allowed within the window
) -> list[bool]:
For each request at timestamp t, count how many already-allowed requests fall within the window (t - windowLength, t]. If that count is already maxRequests, deny the current request (return False); otherwise allow it (return True) and record it.
Example:
requestTimestamps=[1,2,3,4,5,6], windowLength=3, maxRequests=2[True, True, False, True, True, False]Level 2 — Per-Entity Rate Limiter (Follow-up)
Extend the rate limiter to enforce independent sliding-window limits per userId AND per experienceId. A request is denied if either the per-user limit or the per-experience limit is exceeded.
def per_entity_rate_limiter(
requestTimestamps: list[int],
userIds: list[int],
experienceIds: list[str],
windowLength: int,
maxRequests: int
) -> list[bool]:
Example:
requestTimestamps=[1,2,3,4,5], userIds=[1,1,2,1,2], experienceIds=["A","A","A","A","B"], windowLength=3, maxRequests=1[True, False, False, True, True]Only allowed requests should be recorded in the per-entity queues (i.e., denied requests do not count against future limits).
Now extend to rate limit independently per userId AND per experienceId. A request is denied if either constraint is violated.
What if a request has many arbitrary fields (not just userId and experienceId) that each need independent rate limiting?
Extend to per-IP rate limiting instead of (or in addition to) userId/experienceId. (when: After Level 2 (variant))
What is the time and space complexity of your solution?
How would you handle garbage collection of stale entries (entities that haven't had requests in a long time)?
| Approach | Notes |
|---|---|
| Sets / sorted containers per entity | One variant mentioned using sets; provides O(log n) insertion and range queries but more complex than a simple deque; useful if timestamps are not necessarily sorted. |
| Token bucket / fixed window counter | Simpler to implement but less accurate—fixed windows can allow burst at window boundaries; sliding window is the canonical ask here. |
Common mistakes: Not correctly handling the condition for evicting stale timestamps from the deque — the boundary check (strict vs. inclusive) was the most common source of wrong answers on hidden test cases.; Spending too much time on Level 1 (compile errors, debugging brackets, typos) and then running out of time to finish Level 2, causing a fail.; Writing a main() function or extra boilerplate before realizing only the function body needed to be submitted, wasting significant time.; For Level 2, not correctly maintaining both the user deque and the experience deque — updating one but forgetting the other when a request is denied, leading to state corruption.
Interviewer hints: When a candidate got the window eviction logic wrong, the interviewer provided hints rather than letting them spin — but it still counted against them.; The interviewer noticed a typo bug in one candidate's code but the test cases were not thorough enough to catch it; the interviewer mentioned it explicitly after the fact.; After Level 2, the interviewer asked about time and space complexity.; The platform has both visible and hidden test cases; hidden cases are not shown even if they fail, so candidates could not see what they missed.
What passers do: Used a deque (queue) for Level 1 and a dict of deques for Level 2, which is the canonical solution the interviewers expected.; Passed even with hidden test cases not fully covered — interviewers weigh approach and communication heavily, not just perfect output.; Finished Level 1 quickly and moved on to Level 2; candidates who spent too long on Level 1 ran out of time on Level 2 and failed.; Caught their own bugs (typos, off-by-one in window boundary) before the interviewer flagged them, or found discrepancies in the system's own solution.
Send them this page. It is free to read, no account needed.
What you just read — canonical solution, follow-up arc, what passing candidates actually did — exists for all 34 Roblox questions, refreshed monthly from new candidate reports.