FastPrep
Problem · Sliding Window

Accept or Decline Queries

● MediumRampOA

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.

    Examples
    01 · Example 1
    timestamps = ["1600040547954", "1600040547957", "1600040547958"]
ipAddresses = ["127.127.420.312", "127.127.420.312", "127.127.420.312"]
limit = 1
timeWindow = 3
return = [1, 0, 1]
    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.
    02 · Example 2
    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
return = [1, 1, 1, 0, 1, 1, 1]
    :)
    drafts saved locally
    public int[] acceptOrDeclineQueries(String[] timestamps, String[] ipAddresses, int limit, int timeWindow) {
  // write your code here
}
    timestamps["1600040547954", "1600040547957", "1600040547958"]
    ipAddresses["127.127.420.312", "127.127.420.312", "127.127.420.312"]
    limit1
    timeWindow3
    expected[1, 0, 1]
    sign in to submit