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.

Examples

Example 1

• Input: requests = [[1, 42], [2, 42], [3, 42], [4, 42]], limit = 2, window_size = 3
• Output: [True, True, False, True]
• Explanation: At time 3, user 42 already has accepted requests at times 1 and 2 within window [1, 3], so the third is rejected.

Example 2

• Input: requests = [[5, 1], [5, 2], [6, 1], [7, 1]], limit = 2, window_size = 2
• Output: [True, True, True, False]
• Explanation: For user 1 at time 7, accepted requests at times 6 and 7 would exceed the limit in window [6, 7].

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