Rate Limiter Implementation

Your task is to implement a Rate Limiter. Given a list of timestamped queries, you will need to accept or decline each of them, depending on the number of requests from the same IP during a given window of time.

The queries are represented by the two arrays timestamps and ipAddresses.

Request Arrays

• timestamps is an array of integers representing the Unix timestamps of the requests. timestamps[i] represents the timestamp for the iᵗʰ request, in milliseconds. It is guaranteed that all requests are in chronological order, i.e., the timestamps array is sorted in non-decreasing order. It is also guaranteed that no two requests from the same IP address have the same timestamp.
• ipAddresses is an array of strings representing source IP addresses. ipAddresses[i] corresponds to the IP address of the iᵗʰ request.

You are also given two integers limit and timeWindow:

• limit represents the maximum number of requests that can be accepted from the same IP address, within the time window.
• timeWindow represents the duration of the inclusive time window, in milliseconds.

Expected Output

Your task is to return an array of integers where the iᵗʰ element of the array corresponds to the iᵗʰ request. Each element of the array you return should equal to 1 if the iᵗʰ request has been accepted, and 0 if the request has been declined.

Focus first on getting a basic solution working to handle fewer than 1000 requests and window sizes smaller than 40, and confirm this is working with test cases 1–9. Then, optimize your solution to handle the following efficiently to pass test cases 10–20:

• High load – handling up to 10⁵ queries
• Large window size – handling window size of up to 10⁹ milliseconds

Note: even though you are given all the requests at once, assume they come serially. That is, you don’t know anything about the next request when answering the iᵗʰ request – that’s how a rate limiter is supposed to work in real life.

Example

Example 1

timestamps = [1600040547954, 1600040547957, 1600040547958]
ipAddresses = ["127.105.232.211", "127.105.232.211", "127.105.232.211"]
limit = 1
timeWindow = 3
# Output: [1, 0, 1]

Let's consider all the requests one by one:

• The first request has arrived at timestamp 1600040547954 from IP address "127.105.232.211", and since there are no accepted requests from the same IP address during the last timeWindow = 3ms, the first request is accepted.
• The second request has arrived at timestamp 1600040547957 from IP address "127.105.232.211", and since there is already one accepted request from the same IP address during the last timeWindow = 3ms and limit = 1, the second request is declined.
• The third request has arrived at timestamp 1600040547958 from IP address "127.105.232.211", and since there are no other accepted requests from the same IP address during the last timeWindow = 3ms, the third request is accepted. Note that since the second request has been declined, it isn’t counted here.

Example 2

timestamps = [1600000000000, 1600000000000, 1600000000001]
ipAddresses = ["56.75.0.49", "62.2.159.38", "62.2.159.38"]
limit = 2
timeWindow = 10
# Output: [1, 1, 1]

There were no more than two requests from each IP address which fits into the limit = 2. Thus, all requests should be accepted.

Input/Output

Execution Constraints

• Execution time limit: 3 seconds (Java)
• Memory limit: 1 GB

Input

array.integer64 timestamps

An array of Unix timestamps for each of the requests, in milliseconds. It is guaranteed that the array is non-decreasing and no two requests from the same IP address have the same timestamp.

Guaranteed constraints:

1 ≤ timestamps.length ≤ 10⁵
10⁴ ≤ timestamps[i] ≤ 10¹¹ + 10³

array.string ipAddresses

An array of IP addresses for each of the requests. It is guaranteed that all given IPs are valid, i.e., they are in the range ["0.0.0.0", "255.255.255.255"].

Guaranteed constraints:

ipAddresses.length == timestamps.length
7 ≤ ipAddresses[i].length ≤ 15

integer limit

The maximal amount of requests from the same IP address within every timeWindow milliseconds.

Guaranteed constraints:

1 ≤ limit ≤ timestamps.length

integer timeWindow

The window size, in milliseconds.

Guaranteed constraints:

1 ≤ timeWindow ≤ 10⁹

Output

array.integer

An array of 0s and 1s representing whether the request has been accepted or declined.

Java Syntax Tips

// Prints help message to the console
// Returns a string
//
// Globals declared here will cause a compilation error,
// Declare variables inside the function instead!
String helloWorld(String name) {
    System.out.println("This prints to the console when you Run Tests");
    return "Hello, " + name;
}

我们长期稳定承接各大科技公司如TikTok、Google、Amazon等的OA笔试代写服务，确保满分通过。如有需求，请随时联系我们。

We consistently provide professional online assessment services for major tech companies like TikTok, Google, and Amazon, guaranteeing perfect scores. Feel free to contact us if you're interested.