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 Onsite 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 queue-based rate limiter with multi-key limits

Quick Overview

This question evaluates implementation and design skills around rate limiting, including rolling-window counters, multi-key constraints, and atomic updates, and falls under the Coding & Algorithms domain focused on practical application of algorithms and data structures.

Company: Roblox

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: Medium

Interview Round: Onsite

Implement a rate limiter with method allow(timestamp) that returns true if a request is allowed under a limit of K requests per rolling window W milliseconds, otherwise false. Assume timestamps are nondecreasing integers. Then extend the API to allow(userId, experience, timestamp) that enforces independent limits: at most Ku requests per W per userId and at most Ke requests per W per experience value. The call should succeed only if both limits are satisfied and it must update both counters atomically. Discuss time and space complexity and how you would garbage-collect stale keys.

Quick Answer: This question evaluates implementation and design skills around rate limiting, including rolling-window counters, multi-key constraints, and atomic updates, and falls under the Coding & Algorithms domain focused on practical application of algorithms and data structures.

Part 1: Rolling Window Queue Rate Limiter

Implement a function that simulates a queue-based rate limiter. You are given integers K and W and a nondecreasing list of request timestamps. For each timestamp t, the request is allowed if fewer than K previously allowed requests have timestamps strictly greater than t - W, meaning they are still inside the last W milliseconds. If the request is allowed, record it; rejected requests do not consume capacity. Return a boolean result for every request in order.

Constraints

1 <= K <= 10^5
1 <= W <= 10^9
0 <= len(timestamps) <= 2 * 10^5
0 <= timestamps[i] <= 10^9
timestamps is sorted in nondecreasing order

Examples

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

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

Explanation: At time 3, the allowed requests at 1 and 2 are still inside the last 5 ms, so the third request is denied. By time 6, timestamp 1 has expired.

Input: (1, 3, [5, 5, 8, 8])

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

Explanation: Requests at the same timestamp count toward the same window. A request at time 5 expires when the current time reaches 8.

Input: (3, 10, [])

Expected Output: []

Explanation: Edge case: no requests.

Input: (3, 10, [100])

Expected Output: [True]

Explanation: Edge case: a single request is allowed.

Input: (2, 1, [0, 0, 1, 1])

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

Explanation: With W = 1, timestamps equal to current_time - 1 are expired, so both requests at time 0 are gone before processing time 1.

Hints

Keep only allowed request timestamps that are still inside the current rolling window.
A deque is a natural fit because expired timestamps always leave from the front.

Part 2: Atomic Multi-Key Rate Limiter

Extend the rate limiter to enforce two independent rolling-window limits at the same time. You are given Ku, Ke, W, and a nondecreasing list of requests in the form (userId, experience, timestamp). A request is allowed only if both of these are true among previously allowed requests whose timestamps are strictly greater than timestamp - W: the same userId appears fewer than Ku times, and the same experience appears fewer than Ke times. If a request is allowed, record it in both the user and experience counters. If it is denied by either rule, record nothing in either counter; the update must be atomic. Return a boolean result for every request in order. Empty per-key queues may be deleted after pruning to garbage-collect stale keys.

Constraints

1 <= Ku, Ke <= 10^5
1 <= W <= 10^9
0 <= len(requests) <= 2 * 10^5
userId and experience are strings
0 <= timestamp <= 10^9
request timestamps are sorted in nondecreasing order

Examples

Input: (1, 2, 5, [('u1', 'A', 1), ('u1', 'A', 2), ('u2', 'A', 2)])

Expected Output: [True, False, True]

Explanation: The second request is blocked by the per-user limit. Because the update is atomic, it does not consume experience A capacity, so the third request is still allowed.

Input: (2, 1, 4, [('u1', 'A', 1), ('u2', 'A', 2), ('u2', 'B', 2), ('u3', 'A', 5)])

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

Explanation: The second request is denied by the per-experience limit for A. At time 5, the earlier A request at time 1 has expired.

Input: (2, 2, 10, [])

Expected Output: []

Explanation: Edge case: empty request list.

Input: (2, 2, 3, [('u1', 'E1', 0), ('u1', 'E2', 0), ('u1', 'E3', 0), ('u2', 'E1', 0), ('u2', 'E1', 3)])

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

Explanation: u1 reaches its per-user limit after the first two requests, so the third is denied. At time 3, all timestamp 0 entries have expired because W = 3.

Input: (1, 1, 1, [('u1', 'X', 10), ('u1', 'X', 10), ('u1', 'X', 11)])

Expected Output: [True, False, True]

Explanation: Boundary case: the allowed request at time 10 expires exactly when processing time 11.

Hints

Maintain one hash map of deques for userId counts and another for experience counts.
Prune expired timestamps first, then check both limits, and append to both deques only if both checks pass.

Quick Overview