How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a medium difficulty Coding & Algorithms question, commonly asked during Technical Screen rounds at Roblox.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Roblox during technical interviews.

Implement Sliding-Window Rate Limiter | Roblox Coding Question

Implement Sliding-Window Rate Limiter

Company: Roblox

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

You are asked to build an in-memory rate limiter for an API service. For each `user_id`, allow at most `limit` requests during any rolling window of `window_seconds` seconds. Implement a class with the following interface: - `RateLimiter(limit: int, window_seconds: int)` - `allow(user_id: str, timestamp: int, request_id: str | None = None) -> bool` Behavior: 1. Requests arrive in nondecreasing `timestamp` order. 2. A request should be accepted only if the user has made fewer than `limit` accepted requests in the interval `[timestamp - window_seconds + 1, timestamp]`. 3. Requests that fall outside the current sliding window must be removed efficiently. 4. `allow` returns `true` if the current request is accepted and `false` otherwise. Follow-up: if `request_id` is provided, repeated requests with the same `request_id` from the same user within the active window should be treated as duplicates and should not consume additional quota. Explain how you would extend the data structure with a set to support this efficiently.

Quick Answer: This question evaluates understanding of time-based sliding-window rate limiting, per-user quota enforcement, efficient in-memory data structures for time-series event eviction, and optional duplicate-detection using request IDs.

Part 1: Implement Sliding-Window Rate Limiter

Given limit, window_seconds, and a chronological list of API requests, simulate a sliding-window rate limiter. Each request is a pair (user_id, timestamp). A request is accepted only if that user has made fewer than limit previously accepted requests in the inclusive interval [timestamp - window_seconds + 1, timestamp]. Rejected requests do not count toward future quota. Return the decision for every request in order.

Constraints

1 <= limit <= 10^5
1 <= window_seconds <= 10^9
0 <= len(requests) <= 2 * 10^5
timestamps are integers in nondecreasing order
user_id is a string
Rate limits are tracked independently for each user

Examples

Input: (2, 5, [('u1', 1), ('u1', 2), ('u1', 3), ('u1', 6)])

Expected Output: [True, True, False, True]

Explanation: At time 3, user u1 already has two accepted requests in [ -1, 3 ], so the third is rejected. At time 6, the request at time 1 has expired from the window [2, 6].

Input: (1, 3, [('a', 1), ('b', 1), ('a', 2), ('b', 4), ('a', 4)])

Expected Output: [True, True, False, True, True]

Explanation: Each user has an independent limit. User a is blocked at time 2 by the accepted request at time 1, but can send again at time 4 after the old request expires.

Input: (3, 10, [])

Expected Output: []

Explanation: Edge case: no requests means no decisions to return.

Input: (1, 3, [('u', 1), ('u', 3), ('u', 4)])

Expected Output: [True, False, True]

Explanation: The window is inclusive. At time 3, the request at time 1 is still inside [1, 3], so the second request is rejected. At time 4, that old request has expired from [2, 4].

Hints

Because timestamps never decrease, each user's accepted timestamps can be stored in a queue or deque.
Before deciding on a request at time t, remove all accepted timestamps strictly smaller than t - window_seconds + 1 from the front.

Part 2: Extend the Rate Limiter with request_id Deduplication

Now each API request also includes request_id, so each request is a triple (user_id, timestamp, request_id). Build the same sliding-window rate limiter, but add deduplication per user: if request_id is not None and matches an already accepted request from the same user that is still active in the current sliding window, return True immediately and do not consume additional quota. A duplicate does not create a new stored request and does not extend the lifetime of the original accepted request. If request_id is None, process the request normally with no deduplication. Rejected requests are not added to the deduplication structure.

Constraints

1 <= limit <= 10^5
1 <= window_seconds <= 10^9
0 <= len(requests) <= 2 * 10^5
timestamps are integers in nondecreasing order
user_id is a string
request_id is either a string or None
Deduplication is scoped to a single user only

Examples

Input: (2, 5, [('u', 1, 'r1'), ('u', 2, 'r1'), ('u', 3, 'r2'), ('u', 4, 'r3')])

Expected Output: [True, True, True, False]

Explanation: The second request is a duplicate of an active accepted request, so it returns True without using quota. That leaves room for r2, but not for r3.

Input: (1, 3, [('u', 1, 'r1'), ('u', 3, 'r1'), ('u', 4, 'r1')])

Expected Output: [True, True, True]

Explanation: At time 3, r1 is still active and is treated as a duplicate. At time 4, the original accepted request at time 1 has expired, so r1 is treated as a new request and can be accepted again.

Input: (1, 5, [('u', 1, 'a'), ('u', 2, 'b'), ('u', 6, 'b')])

Expected Output: [True, False, True]

Explanation: The request with id b at time 2 was rejected, so it was never added to the active deduplication set. After the old accepted request expires, b can be accepted at time 6.

Input: (2, 4, [('a', 1, None), ('a', 2, None), ('a', 2, None)])

Expected Output: [True, True, False]

Explanation: request_id = None means no deduplication. These behave like ordinary requests, so the third one exceeds the limit.

Input: (3, 10, [])

Expected Output: []

Explanation: Edge case: no requests produces an empty list.

Hints

Keep a deque of accepted requests per user, storing both timestamp and request_id so expired entries can be removed from the window.
Use a per-user set of active request_id values. When an accepted request expires from the deque, remove its request_id from the set too.

Quick Overview

This question evaluates understanding of time-based sliding-window rate limiting, per-user quota enforcement, efficient in-memory data structures for time-series event eviction, and optional duplicate-detection using request IDs.