Sliding Window API Rate Limiter | Dataford Interview Questions

Your question is Sliding Window API Rate Limiter. Start with the requirements on the right.

Run and submit as often as you like. When you're ready, talk me through your approach or go straight to the code.

Problem

Meta wants to protect an internal API endpoint used by systems like TAO-backed services from bursts of traffic. Implement a per-user sliding window rate limiter that decides whether each request should be allowed.

Given a list of request events sorted by non-decreasing timestamp, determine for each event whether it is accepted under the rule: a user may make at most limit requests in any rolling interval of window_size seconds, inclusive of the current timestamp.

Formal Specification

Implement a function:

Input: requests: List[List[int]], where each element is [timestamp, user_id]
Input: limit: int
Input: window_size: int
Output: List[bool], where result[i] is True if requests[i] is allowed, otherwise False

A request at time t counts all previously accepted requests for the same user with timestamp >= t - window_size + 1 and <= t.

Constraints

1 <= len(requests) <= 2 * 10^5
1 <= limit <= 10^5
1 <= window_size <= 10^9
0 <= timestamp <= 10^9
1 <= user_id <= 10^9
requests is sorted by non-decreasing timestamp

Function Signature

def rate_limiter(requests, limit, window_size):