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.
Implement a function:
requests: List[List[int]], where each element is [timestamp, user_id]limit: intwindow_size: intList[bool], where result[i] is True if requests[i] is allowed, otherwise FalseA request at time t counts all previously accepted requests for the same user with timestamp >= t - window_size + 1 and <= t.
Example 1
requests = [[1, 42], [2, 42], [3, 42], [4, 42]], limit = 2, window_size = 3[True, True, False, True][1, 3], so the third is rejected.Example 2
requests = [[5, 1], [5, 2], [6, 1], [7, 1]], limit = 2, window_size = 2[True, True, True, False][6, 7].1 <= len(requests) <= 2 * 10^51 <= limit <= 10^51 <= window_size <= 10^90 <= timestamp <= 10^91 <= user_id <= 10^9requests is sorted by non-decreasing timestamprequests = [[1, 42], [2, 42], [3, 42], [4, 42]], limit = 2, window_size = 3Output[True, True, False, True]WhyAt time 3, user 42 already has two accepted requests in window [1, 3], so that request is rejected. At time 4, the request at time 1 has expired, so the new request is allowed.requests = [[5, 1], [5, 2], [6, 1], [7, 1]], limit = 2, window_size = 2Output[True, True, True, False]WhyUsers are tracked independently. For user 1 at time 7, accepted requests at times 6 and 7 would exceed the limit in window [6, 7], so it is rejected.1 <= len(requests) <= 2 * 10^51 <= limit <= 10^51 <= window_size <= 10^90 <= timestamp <= 10^91 <= user_id <= 10^9requests is sorted by non-decreasing timestampdef rate_limiter(requests, limit, window_size):