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

What role is this question designed for?

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

Implement a sliding-window rate limiter

Company: Reddit

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Onsite

## Problem Design and implement an in-memory **rate limiter** using a **sliding time window**. You are given a stream of requests. Each request has: - `key` (e.g., user ID, API token, or IP) - `timestamp` (integer seconds, non-decreasing for a given `key`) Implement an API: - `bool allow(key, timestamp)` The limiter should allow **at most `N` requests per `W` seconds** for each `key`. ### Requirements - If a request is allowed, it counts toward the limit. - Sliding window means the window is `(timestamp - W, timestamp]` (or clearly define inclusivity and keep it consistent). - Support many distinct keys. ### Example If `N = 3`, `W = 10` seconds: - Requests for the same key at times `[1, 2, 3]` are allowed. - A request at time `4` is denied (already 3 in last 10 seconds). - A request at time `12` may be allowed depending on the sliding window definition (e.g., requests at time `1` may have expired). ### Constraints (assumptions you may use) - Timestamps fit in 64-bit integer. - Aim for near O(1) average time per `allow` call. - Memory should not grow unbounded for inactive keys (you may describe a cleanup strategy).

Quick Answer: This question evaluates a candidate's ability to implement a sliding-window rate limiter, emphasizing time-based algorithms, per-key state management, and efficient data-structure choices to achieve near-O(1) operations.

Given integers limit N and window W, plus a list of requests, simulate an in-memory sliding-window rate limiter. Each request is a pair (key, timestamp). For every request, decide whether allow(key, timestamp) should return True or False, and return the decisions in order. A request for a key at time t is allowed if fewer than N previously allowed requests for that same key have timestamps x such that t - W < x <= t. If the request is allowed, its timestamp is stored for that key; if denied, it does not count toward the limit. Keys are independent, and requests for the same key appear in non-decreasing timestamp order. Store only timestamps that are still relevant to the current window for each key. In a real service, fully inactive keys could be removed lazily or by background cleanup; you do not need to implement global eviction beyond expiring old timestamps when a key is processed.

Constraints

1 <= limit <= 10^5
1 <= window <= 10^18
0 <= len(requests) <= 2 * 10^5
For the same key, timestamps in the input are non-decreasing
A denied request does not count toward future limits

Examples

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

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

Explanation: The first three requests are allowed. At time 4, key 'u1' already has 3 allowed requests in the window (-6, 4], so it is denied. At time 12, the window is (2, 12], so timestamps 1 and 2 have expired and the request is allowed.

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

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

Explanation: Each key is limited independently. For 'a', requests at 1 and 2 are allowed, so the request at 3 is denied. At time 4 for 'a', timestamp 1 has expired because the window is (1, 4], so that request is allowed. Key 'b' follows the same logic independently.

Input: (3, 10, [])

Expected Output: []

Explanation: No requests means no decisions to return.

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

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

Explanation: With limit 1 and window 1, only one allowed request can exist in (t - 1, t]. The second request at time 100 is denied. At time 101, the request from 100 has expired because 100 <= 101 - 1, so one request is allowed again; the next request at 101 is denied.

Solution

from collections import defaultdict, deque

def solution(limit, window, requests):
    buckets = defaultdict(deque)
    result = []

    for key, timestamp in requests:
        q = buckets[key]
        cutoff = timestamp - window

        while q and q[0] <= cutoff:
            q.popleft()

        if len(q) < limit:
            q.append(timestamp)
            result.append(True)
        else:
            result.append(False)

    return result

Time complexity: O(r) total, amortized O(1) per request, where r is the number of requests. Space complexity: O(a), where a is the number of allowed timestamps currently stored across all keys.

Hints

Use a hash map from key to a queue/deque of timestamps that were actually allowed for that key.
Before checking a new request at time t, remove all timestamps <= t - window from that key's deque.

Quick Overview

This question evaluates a candidate's ability to implement a sliding-window rate limiter, emphasizing time-based algorithms, per-key state management, and efficient data-structure choices to achieve near-O(1) operations.