Customer Window Rate Limit
MediumDesign · Atlassian
You are building a rate limiter. Each customer may have at most limit accepted requests in any window of window time units.
requests is a list of [timestamp, customer_id] rows in nondecreasing timestamp order. Process them in order. A request at time t from customer c is accepted if, among the requests from c that were already accepted, fewer than limit have a timestamp s with t - s < window. Otherwise it is rejected.
Rejected requests are not recorded and never count against later requests. Requests from different customers never affect each other.
Return a list of booleans, True for accepted and False for rejected, in the same order as requests.
Example 1
- Input:
- requests = [[0, "acme"], [3, "acme"], [5, "acme"], [10, "acme"], [11, "acme"]], limit = 2, window = 10
- Output:
- [True, True, False, True, False]
- Explanation
- The requests at 0 and 3 are accepted. At 5 both are still inside the window (5 and 2 time units old), so the limit of 2 is reached and it is rejected. At 10 the request from 0 has aged out (10 - 0 is not less than 10), leaving one, so it is accepted. At 11 the requests from 3 and 10 are both live, so it is rejected.
Example 2
- Input:
- requests = [[1, "a"], [1, "b"], [1, "a"], [2, "b"]], limit = 1, window = 5
- Output:
- [True, True, False, False]
- Explanation
- Each customer gets one request per 5 time units. The second request from
aand frombeach arrive while their own first request is still live.
Example 3
- Input:
- requests = [[0, "x"], [4, "x"], [8, "x"]], limit = 1, window = 4
- Output:
- [True, True, True]
- Explanation
- Each request arrives exactly 4 units after the previous accepted one, and a request that old no longer counts with
window = 4.
Constraints
0 <= requests.length <= 10^50 <= timestamp <= 10^9, nondecreasing1 <= limit <= 10^51 <= window <= 10^9customer_idis a non-empty string