← 返回 roblox 的题目列表Design a Sliding Window Rate Limiter with Per-IP Limits
类型：online_judge
Problem: Implement a Sliding Window Per-IP Rate Limiter
Implement a sliding-window rate limiter. The system receives a sequence of requests. Each request contains:
timestamp: the arrival time in seconds, represented as an integer;
ip: the source IP address as a string.
Given:
limit = K: each IP can have at most K allowed requests in any sliding window of length window = W seconds;
rejected requests do not count toward future rate-limit checks;
different IPs are rate-limited independently.
For each request, if the number of already allowed requests from the same IP in the interval (timestamp - W, timestamp] is less than K, allow the request and output true; otherwise reject it and output false.
Input Format
K W
Q
timestamp_1 ip_1
timestamp_2 ip_2
...
timestamp_Q ip_Q
Requests are given in non-decreasing order of timestamp.
Output Format
For each request, output one line:
true
or
false
Constraints
1 <= K <= 10^5
1 <= W <= 10^9
1 <= Q <= 2 * 10^5
timestamp is a non-negative integer, and all requests are globally non-decreasing by timestamp
ip is a non-empty string
Example
Input:
2 10
5
1 1.1.1.1
2 1.1.1.1
3 1.1.1.1
11 1.1.1.1
12 1.1.1.1
Output:
true
true
false
true
true
Explanation:
Requests at time 1 and 2 are allowed;
At time 3, the same IP already has 2 allowed requests in (3 - 10, 3], so it is rejected;
At time 11, the request at time 1 is no longer inside (1, 11], so the new request can be allowed.
Example
Input
2 10
5
1 1.1.1.1
2 1.1.1.1
3 1.1.1.1
11 1.1.1.1
12 1.1.1.1
Output
true
true
false
true
true