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.

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.

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].

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]

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]

Approach

The solution simulates two independent sliding windows (per-user and per-game) over requests that arrive in non-decreasing timestamp order, and accepts a request only if both windows currently hold fewer than their respective limits. Data structures - user_windows / game_windows: dicts mapping each id to a deque of the timestamps of its accepted requests still inside the window. - global_window: a single FIFO deque of (timestamp, user_id, game_id) for every accepted request, used to drive eviction. Per request (user_id, game_id, timestamp) 1. Compute start = timestamp - window_ms + 1 (the window is the half-open-style inclusive range [start, timestamp]). 2. Evict stale entries: while the oldest global entry has time < start, pop it and remove its matching front element from that user's and that game's deque (deleting empty deques). Because requests are processed in non-decreasing time, each per-id deque is also sorted, so the stale element is always at the front — the dq[0] == old_time guard makes this safe. 3. Read (or lazily create) the user's and game's deques and check len(user_dq) < user_limit and len(game_dq) < game_limit. 4. If allowed, append timestamp to both deques and the global window; record the boolean. Why it's correct: a single shared global queue keeps eviction O(1) amortized while still expiring each id's counts in lockstep, so the counts checked in step 3 reflect exactly the accepted requests within [start, timestamp]. Rejected requests are never recorded, matching the spec. The early user_limit <= 0 or game_limit <= 0 guard handles the zero-limit case where nothing can ever pass.

Time complexity: O(R) total for R requests (O(1) amortized each): every accepted request is pushed once and evicted at most once from the global queue and from its user/game deque, and each rejection is O(1).

Space complexity: O(A + U + G), where A is the number of accepted requests currently inside the window (across all global/user/game deques), and U, G are the counts of users and games with non-empty deques.

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.

Approach

The solution simulates a per-user sliding-window rate limiter in O(1) amortized time by maintaining two synchronized deques.

Data structures:

user_windows: dict[user_id -> deque] holding the timestamps of each user's currently-active allowed requests.
global_window: one deque of (timestamp, user_id) for all accepted requests, in arrival order.

Why the global deque works: requests arrive in non-decreasing timestamp order, so every per-user deque and the global deque stay sorted by time with the oldest entry at the front. That lets eviction be a cheap front-pop instead of a scan.

Per request (user_id, timestamp):

Compute start = timestamp - window_ms + 1 (inclusive window left edge).
Evict expired entries from the global front while global_window[0][0] < start. For each evicted (old_time, old_user), pop the matching head of that user's deque (the dq[0] == old_time guard keeps the two deques in sync), and delete the user's key once its deque empties — this bounds memory to only active users.
Look up (or create) the user's deque. The request is allowed iff len(dq) < limit, i.e. fewer than limit of this user's prior allowed requests remain in the window.
If allowed, append timestamp to both dq and global_window.

The limit <= 0 short-circuit returns all False. Correctness follows because only allowed requests are recorded, expired ones are removed before each count, and same-timestamp ties are resolved by list order (earlier processed first), exactly as specified.

Key insight: the global deque turns "evict all users' stale entries" into amortized O(1) work — each accepted request is pushed once and popped at most once from each deque.

Time complexity:

O(R) total for R requests (O(1) amortized each): every accepted request is appended once and evicted once from both deques; rejected requests do constant work.

Space complexity:

O(A + U): A = accepted requests still inside the current window (stored in both the global and per-user deques), U = users with non-empty deques; empty user entries are deleted to keep this bounded.