← 返回 rippling 的题目列表Design and Implement a Sliding Window Rate Limiter
类型：online_judge
Problem: Implement a Sliding Window Rate Limiter
Implement a per-user rate limiter.
You are given:
limit: the maximum number of allowed requests per user within a time window;
window: the length of the time window in seconds;
a list of requests, where each request contains:
timestamp: the request time in seconds;
user_id: the user who sends the request.
For each request, determine whether it should be allowed.
Rules:
For a user at current time t, only previously allowed requests in the range [t - window + 1, t] are counted;
If the number of allowed requests in that range is less than limit, the current request is allowed and its timestamp is recorded;
Otherwise, the request is rejected and must not be recorded;
Different users are rate-limited independently;
Request timestamps are given in non-decreasing order.
Input Format
The first line contains three integers:
limit window q
where:
limit is the maximum number of allowed requests in a window;
window is the window length;
q is the number of requests.
The next q lines each contain:
timestamp user_id
Output Format
For each request, print one line:
true if the request is allowed;
false otherwise.
Constraints
1 <= limit <= 10^5
1 <= window <= 10^9
1 <= q <= 2 * 10^5
0 <= timestamp <= 10^18
user_id is a non-empty string with length at most 64
Request timestamps are in non-decreasing order
Example
Input:
2 10 5
1 u1
2 u1
3 u1
11 u1
12 u1
Output:
true
true
false
true
true
Example
Input
2 10 5
1 u1
2 u1
3 u1
11 u1
12 u1
Output
true
true
false
true
true