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.

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

Hints

  1. Track state per user independently — a hash map from userId to that user's recent allowed timestamps.
  2. 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.
  3. Allow the request iff the deque size after eviction is strictly less than maxRequests; only then append t. Never record a denied request.
  4. 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.

Loading coding console...