Rate Limiter

Problem Description

Your task is to implement a Rate Limiter. Given a list of timestamped queries, you 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 two arrays: timestamps and ipAddresses.

• timestamps is an array of integers representing the Unix timestamps of the requests in milliseconds. All timestamps are in non-decreasing order.
• ipAddresses is an array of strings representing source IP addresses. ipAddresses[i] corresponds to the IP address of the i-th request.

You are also given two integers: limit and timeWindow.

• limit: The maximum number of requests that can be accepted from the same IP within the timeWindow.
• timeWindow: The inclusive duration window in milliseconds.

Output Requirement

Return an array of integers where the i-th element is:

• 1 if the i-th request is accepted.
• 0 if the request is declined.

The rate limiter must function serially — each request must be evaluated one at a time without knowledge of future requests.

Constraints

• 1 ≤ timestamps.length
• 1 ≤ limit ≤ 10^6
• 1 ≤ timeWindow ≤ 10^9

Example

Input:
timestamps = [160000547954, 160000547957, 160000547958]
ipAddresses = ["127.105.232.211", "127.105.232.211", "127.105.232.211"]
limit = 1
timeWindow = 3

Output:
[1, 0, 1]

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

Output:
[1, 1, 1]

Notes

• Each request is only counted toward the limit if it was accepted.
• An IP’s request is accepted if the number of accepted requests within the time window before (and including) the current request is less than limit.
• Rejected requests do not count toward the windowed limit.

Input/Output

• [input] array.integer64 timestamps: Sorted array of request timestamps.
• [input] array.string ipAddresses: Array of IPs for the requests.
• [input] integer limit: Maximum allowed requests per IP in window.
• [input] integer timeWindow: Duration of the time window (in milliseconds).
• [output] array.integer: Array of 0s and 1s representing request acceptance.

我们长期稳定承接各大科技公司如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.