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 Read.Ai.

What role is this question designed for?

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

Implement a per-user API rate limiter | Read.Ai Coding Question

Implement a per-user API rate limiter

Company: Read.Ai

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Onsite

You are building an API gateway that must enforce per-user rate limits. ## Task Implement a rate limiter with the following API: - `RateLimiter(int maxRequests, int windowSeconds)` - `bool allow(string userId, int timestampSeconds)` `allow(...)` should return: - `true` if the request for `userId` at `timestampSeconds` is allowed - `false` if allowing it would exceed the limit ## Rate limit rule For each user, allow **at most `maxRequests` requests in any rolling window of `windowSeconds` seconds**. More formally, a request at time `t` is allowed iff the number of *previously allowed* requests with timestamps in `[t - windowSeconds + 1, t]` is strictly less than `maxRequests`. ## Notes / Assumptions - `timestampSeconds` is an integer in seconds. - Calls to `allow` may arrive in non-decreasing timestamp order (you may state/assume this; otherwise discuss how you would handle out-of-order input). - The solution should be efficient in time and memory for many users. ## Example If `maxRequests = 3`, `windowSeconds = 10` and a single user sends requests at times: - `1, 2, 3` → allowed - `4` → denied (would be 4 requests in window `[ -5, 4 ]` which effectively includes `1,2,3,4`) - `12` → allowed (window `[3,12]` contains `3` only among allowed requests)

Quick Answer: This question evaluates the ability to implement per-user API rate limiting, testing competency in time-windowed request accounting, per-entity state management, and designing efficient data structures for time-based constraints.

You are building an API gateway that must enforce per-user rate limits using a rolling-window policy. Implement a rate limiter exposing the conceptual API: - `RateLimiter(int maxRequests, int windowSeconds)` - `bool allow(string userId, int timestampSeconds)` For each user, allow **at most `maxRequests` requests in any rolling window of `windowSeconds` seconds**. Formally, a request at time `t` is allowed iff the number of *previously allowed* requests for that user with timestamps in `[t - windowSeconds + 1, t]` is strictly less than `maxRequests`. A denied request is NOT recorded (it does not consume a slot). ## Executable form for this console Because this is a stateful design problem, implement a single function that replays a request stream and returns the per-request decisions: `solution(maxRequests, windowSeconds, requests)` where `requests` is a list of `[userId, timestampSeconds]` pairs given in non-decreasing timestamp order. Return a list of booleans — the result of `allow(...)` for each request, in order. ## Example With `maxRequests = 3`, `windowSeconds = 10`, and requests `[['u1',1],['u1',2],['u1',3],['u1',4],['u1',12]]`: - `1, 2, 3` → allowed - `4` → denied (would be the 4th allowed request in window `[-5, 4]`) - `12` → allowed (window `[3, 12]` contains only the allowed request at `3`) Result: `[True, True, True, False, True]`.

Constraints

1 <= len(requests) <= 10^6 (and may be empty)
0 <= maxRequests <= 10^4
1 <= windowSeconds <= 10^9
timestampSeconds are non-negative integers in non-decreasing order
userId is a non-empty string
A denied request does not count toward the limit (it is not recorded)

Examples

Input: (3, 10, [['u1', 1], ['u1', 2], ['u1', 3], ['u1', 4], ['u1', 12]])

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

Explanation: The given example: 1,2,3 fill the limit; 4 is the 4th in window [-5,4] so denied (and not recorded); by 12 only the request at 3 remains in window [3,12], so 12 is allowed.

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

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

Explanation: Users are limited independently. User a: 1,2 allowed, then 3 denied (window [-1,3] already has 1,2). User b: 1 and 2 allowed (only 2 in its window).

Input: (1, 1, [['x', 5], ['x', 5], ['x', 6], ['x', 6]])

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

Explanation: maxRequests=1, window=1. The first request each second is allowed; the duplicate at the same second is denied. Denied requests do not block the next second.

Input: (3, 10, [])

Expected Output: []

Explanation: Empty request stream yields an empty decision list.

Input: (0, 10, [['u', 1], ['u', 2]])

Expected Output: [False, False]

Explanation: maxRequests=0 means no request can ever be allowed, since size < 0 is never true.

Input: (2, 100, [['solo', 50]])

Expected Output: [True]

Explanation: A single request from a single user is always allowed when maxRequests >= 1.

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

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

Explanation: Window=3, max=2. At t=3 the window [1,3] already holds the allowed 1 and 2, so 3 is denied (not recorded). At t=4 the 1 has aged out, leaving only 2, so 4 is allowed; similarly 5 is allowed after 2 ages out.

Hints

Track state per user independently — a hash map from userId to that user's recent allowed timestamps.
A rolling time window with FIFO eviction is naturally a deque (monotonic queue): on each request, drop timestamps older than t - windowSeconds + 1 from the front.
Allow the request iff the deque size after eviction is strictly less than maxRequests; only then append t. Never record a denied request.
Watch the boundary: the window is inclusive on both ends and spans exactly windowSeconds seconds, so the lower bound is t - windowSeconds + 1, not t - windowSeconds.

Quick Overview

This question evaluates the ability to implement per-user API rate limiting, testing competency in time-windowed request accounting, per-entity state management, and designing efficient data structures for time-based constraints.