Notification Deduplication Window
Learn this problem
Goldman SachsFULLTIMEONSITE INTERVIEWProblem statement
A notification service receives a finite batch of arrivals. The arrays notificationIds and timestamps describe the same n arrivals in order. Each timestamp is measured in seconds, and the timestamps are nondecreasing.
Process each arrival using a 600-second deduplication window:
- An arrival is a duplicate when the same notification ID was seen less than
600seconds earlier. - An arrival exactly
600seconds after the previous sighting is not a duplicate. - Every arrival becomes the new last sighting for its ID, including an arrival that is suppressed as a duplicate.
Return a boolean array in arrival order. Return true for an accepted notification and false for a suppressed duplicate.
Memory requirement
Discard identifiers as soon as their most recent sighting leaves the active window. The retained state must remain proportional to the identifiers still active in the window rather than the total number of processed arrivals.
Function
deduplicateNotifications(notificationIds: String[], timestamps: int[]) → boolean[]Examples
Example 1
notificationIds = ["A","B","A","A"]timestamps = [0,100,599,1199]return = [true,true,false,true]The arrival of A at 599 is suppressed because it is 599 seconds after the first A. That duplicate refreshes the last-seen time to 599. The final A arrives exactly 600 seconds later, so it is accepted.
Example 2
notificationIds = ["X","X","Y","X","Y"]timestamps = [42,42,42,641,642]return = [true,false,true,false,true]The second X is a duplicate at the same timestamp. The X at 641 is still inside its window, while the Y at 642 is exactly 600 seconds after its previous sighting and is accepted.
Example 3
notificationIds = ["N","N","N","N"]timestamps = [10,609,1208,1808]return = [true,false,false,true]Each suppressed arrival refreshes N, so the arrivals at 609 and 1208 remain duplicates. The final arrival is exactly 600 seconds after the refreshed time 1208 and is accepted.
Constraints
1 <= n <= 2 * 10^5notificationIds.length == timestamps.length == n- Each value in
notificationIdsis a non-empty opaque identifier string. 0 <= timestamps[i] <= 10^9timestamps[i] <= timestamps[i + 1]for every validi.- Timestamps are measured in whole seconds.