Accept or Decline Queries
Problem statement
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.,
timestampsis 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:
limitrepresents the maximum number of requests that can be accepted from the same IP address, within the time window.timeWindowrepresents 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.
Function
acceptOrDeclineQueries(timestamps: String[], ipAddresses: String[], limit: int, timeWindow: int) → int[]Examples
Example 1
timestamps = ["1600040547954", "1600040547957", "1600040547958"]ipAddresses = ["127.127.420.312", "127.127.420.312", "127.127.420.312"]limit = 1timeWindow = 3return = [1, 0, 1]Request at 0 has arrived at timestamp 1600040547954 from IP address 127.127.420.312, and since there are no accepted requests from 127.127.420.312, it's accepted. Thus 1. Request at 1 has arrived at timestamp 1600040547957 from IP address 127.127.420.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.127.420.312. There are no accepted requests from this IP address within this time window, it's accepted. Thus 1.
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 = 2timeWindow = 3return = [1, 1, 1, 0, 1, 1, 1]:)
Source note: This source image shows the reported Ramp online-assessment examples for the per-IP sliding-window rate limiter.