Problem Brief

Accept or Decline Queries

Hi! I made a tiny modification in the input timestamps, it is supposed to be int[], but Java says it is too large as integer, so I have to change it to String[]. Things might be a bit more complicated, but I believe you can handle it :P

Given a list of timestamped queries, you will need to accept or decline each of them, depending on the number of request from the same IP during a given window.

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

timestamps, an array of integers representing the Unix timestamps of the requests.

a. timestamps[i] represents the ith timestamp for the ith request, in milliseconds.

b. All requests are guaranteed to be in chronological order, i.e., timestamps is sorted in non-decreasing order.

c. It's guaranteed that no two requests from the same IP have the same timestamp.

ipAddresses, an array of strings representing source IP addresses.

d. ipAddresses[i] corresponds to the ith request's IP address.

You're 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.

You must return an array of integers where the ith element of the array corresponds to the ith request. Each element of the array should equal to 1 if the ith request was accepted and 0 if it was rejected.

1Example 1

Input

timestamps = ["1600040547954", "1600040547957", "1600040547958"], ipAddresses = ["127.127.420.312", "127.127.420.312", "127.127.420.312"], limit = 1, timeWindow = 3

Output

[1, 0, 1]

Explanation

Request at 0 has arrived at timestamp 1600040547954 from IP address 127.105.456.312, and since there are no accepted requests from 127.105.456.312, it's accepted. Thus 1. Request at 1 has arrived at timestamp 1600040547957 from IP address 127.105.456.312. There's already a request from the same IP address within the same time window so we reject. Thus 0. Request at 2 has arrived at timestamp 1600040547958 from IP address 127.105.456.312. There are no accepted requests from this IP address within this time window, it's accepted. Thus 1.

2Example 2

Input

timestamps = ["52245", "52245", "52246", "52247", "52248", "52249", "52253"], ipAddresses = ["00.00.00.15", "00.00.00.42", "00.00.00.15", "00.00.00.15", "00.00.00.42", "00.00.00.15", "00.00.00.96"], limit = 2, timeWindow = 3

Output

[1, 1, 1, 0, 1, 1, 1]

Explanation