High-Traffic IPs in a Sliding Window
Google● MediumINTERNONSITE INTERVIEWProblem statement
You receive a chronological stream of server requests. The arrays timestamps and ipAddresses describe the same requests, and timestamps[i] is the integer arrival time of ipAddresses[i].
For each IP address, consider every sliding window of the form (t - windowSeconds, t] whose right endpoint t is one of that IP address's request timestamps. An address is high traffic if at least one such window contains strictly more than requestThreshold requests from that address.
Return every high-traffic IP address exactly once, sorted in lexicographic order. Requests with the same timestamp are all inside the same active window.
Process the requests in chronological order without rescanning the full history for every request.
Function
findHighTrafficIps(timestamps: int[], ipAddresses: String[], windowSeconds: int, requestThreshold: int) → String[]Examples
Example 1
timestamps = [1,2,3,12,13]ipAddresses = ["10.0.0.1","10.0.0.1","10.0.0.1","10.0.0.1","10.0.0.2"]windowSeconds = 10requestThreshold = 2return = ["10.0.0.1"]At timestamp 3, the window (-7, 3] contains three requests from 10.0.0.1, which is strictly more than the threshold of two.
Example 2
timestamps = [0,10,10,20]ipAddresses = ["x","x","y","x"]windowSeconds = 10requestThreshold = 1return = []A request exactly windowSeconds before the current timestamp is outside the half-open window. No IP has more than one request in any active window.
Constraints
0 <= timestamps.length == ipAddresses.length <= 200000.0 <= timestamps[i] <= 10^9, andtimestampsis sorted in nondecreasing order.- Every IP address is a non-empty string of at most
64visible ASCII characters. 1 <= windowSeconds <= 10^9.1 <= requestThreshold <= max(1, timestamps.length).