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 a sliding-window rate limiter

Quick Overview

Evaluates the candidate's ability to design and implement an in-memory sliding-window rate limiter enforcing per-user and per-game constraints, focusing on correct request-acceptance semantics and efficient timestamp eviction; Category/domain: Coding & Algorithms; Level of abstraction: component-level algorithm and data-structure implementation.

Company: Roblox

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Onsite

Implement an in-memory **sliding-window rate limiter**. You are given a stream of requests, each with a timestamp in milliseconds. ### Part 1: Per-user limit Design a data structure with an API like: - `bool allow(userId, timestampMs)` Each user has their own limiter: allow at most **N requests per user** in the last **W milliseconds** (a sliding window ending at `timestampMs`, inclusive). Return `true` if the request is allowed and should be recorded; otherwise return `false`. ### Part 2: User limit + game limit Extend it to handle requests that include a `gameId`: - `bool allow(userId, gameId, timestampMs)` Now there are **two independent sliding-window limiters**: 1. A per-user limiter: max **Nu** requests per user per **W** ms. 2. A per-game limiter: max **Ng** requests per game per **W** ms. A request `(userId, gameId, timestampMs)` is allowed **only if both** the user limiter and the game limiter would allow it. If either limiter rejects, the request is rejected. Specify the approach and implement it efficiently for many users/games. Discuss time/space complexity and how you evict old timestamps.

Quick Answer: Evaluates the candidate's ability to design and implement an in-memory sliding-window rate limiter enforcing per-user and per-game constraints, focusing on correct request-acceptance semantics and efficient timestamp eviction; Category/domain: Coding & Algorithms; Level of abstraction: component-level algorithm and data-structure implementation.

Part 1: Per-user Sliding-Window Rate Limiter

Implement solution(limit, window_ms, requests) to simulate an in-memory per-user sliding-window rate limiter. Each request is a tuple (user_id, timestamp_ms). For a request at time t, count only that user's previously allowed requests whose timestamps are in the inclusive window [t - window_ms + 1, t]. If that count is less than limit, allow the request and record it. Otherwise, reject it. Return a list of booleans indicating whether each request is allowed. Requests are processed in the given order. If multiple requests have the same timestamp, earlier ones in the list are processed first and can affect later ones.

Constraints

0 <= limit <= 10^5
1 <= window_ms <= 10^9
0 <= len(requests) <= 2 * 10^5
0 <= timestamp_ms <= 10^12
requests are sorted by non-decreasing timestamp_ms
user_id is a hashable identifier such as a string or integer

Examples

Input: (2, 1000, [('u1', 0), ('u1', 500), ('u1', 999), ('u1', 1000), ('u1', 1500)])

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

Explanation: At time 999, user u1 already has allowed requests at 0 and 500 within the window [0, 999], so the third request is rejected. At time 1000, timestamp 0 expires because the new window is [1, 1000].

Input: (1, 10, [('a', 1), ('b', 1), ('a', 5), ('b', 10), ('a', 11)])

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

Explanation: Each user has an independent limiter. User a is blocked at time 5 because time 1 is still in the window [ -4, 5 ] conceptually, or [1, 5] after clamping to seen timestamps. User b is blocked at time 10 because its earlier request at 1 is still inside [1, 10].

Input: (3, 100, [])

Expected Output: []

Explanation: Edge case: no requests.

Input: (2, 1, [('x', 100), ('x', 100), ('x', 101)])

Expected Output: [True, True, True]

Explanation: With a 1 ms window, only requests from the exact same millisecond count together. Both requests at 100 are allowed because the limit is 2. At 101, the two requests at 100 have expired.

Hints

A deque is useful because old timestamps expire from the left, while new accepted timestamps are appended to the right.
To avoid stale data for users who may not appear again, keep a global deque of accepted events and evict expired events from both the global structure and the matching user's deque.

Part 2: Combined Per-user and Per-game Sliding-Window Rate Limiter

Implement solution(user_limit, game_limit, window_ms, requests) to simulate a rate limiter with two independent sliding-window checks. Each request is a tuple (user_id, game_id, timestamp_ms). A request at time t is allowed only if both conditions hold: 1. The user has fewer than user_limit previously allowed requests with timestamps in [t - window_ms + 1, t]. 2. The game has fewer than game_limit previously allowed requests with timestamps in [t - window_ms + 1, t]. If either check fails, reject the request. Rejected requests must not be recorded in either limiter. Return a list of booleans indicating whether each request is allowed. Requests are processed in the given order. If multiple requests have the same timestamp, earlier ones in the list are processed first and can affect later ones.

Constraints

0 <= user_limit <= 10^5
0 <= game_limit <= 10^5
1 <= window_ms <= 10^9
0 <= len(requests) <= 2 * 10^5
0 <= timestamp_ms <= 10^12
requests are sorted by non-decreasing timestamp_ms
user_id and game_id are hashable identifiers such as strings or integers

Examples

Input: (2, 1, 100, [('u1', 'g1', 0), ('u2', 'g1', 10), ('u1', 'g2', 20), ('u3', 'g1', 50), ('u1', 'g1', 101)])

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

Explanation: Game g1 allows only 1 request per 100 ms window, so the requests at 10 and 50 are rejected because g1 already accepted the request at 0. By time 101, timestamp 0 has expired, so the last request is allowed.

Input: (1, 1, 10, [('u1', 'g1', 1), ('u2', 'g1', 2), ('u2', 'g2', 3), ('u2', 'g2', 4), ('u1', 'g2', 11)])

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

Explanation: The second request is rejected by the game limiter and must not count against user u2. That is why u2 can still be accepted at time 3 on a different game.

Input: (1, 2, 5, [('a', 'x', 0), ('a', 'y', 4), ('a', 'x', 5), ('b', 'x', 5), ('a', 'x', 9)])

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

Explanation: At time 5, the request at time 0 has expired because the active window is [1, 5]. Later, at time 9, user a already has an accepted request at 5 in the window [5, 9], so the request is rejected.

Input: (3, 3, 50, [])

Expected Output: []

Explanation: Edge case: no requests.

Hints

You need one queue per user and one queue per game, but be careful: a rejected request must be added to neither queue.
A global queue of accepted events lets you evict expired timestamps for inactive users or games, so memory only tracks data that can still matter.

Quick Overview