Delayed Streaming Duplicate Suppression
Updated
Problem statement
A logging service receives a stream of statuses in nondecreasing timestamp order. Each status contains an integer timestamp in seconds and a case-sensitive message.
A status is isolated when no other status with the exact same message has an absolute timestamp difference strictly less than 10 seconds. If two equal messages occur within that window, both occurrences are suppressed. This rule can suppress every status in a chain of nearby equal messages.
Because a future arrival may invalidate an earlier status, an implementation must delay a decision until that earlier status's 10-second window has closed. The finite-array interface below represents one complete stream and includes the required end-of-stream flush.
Return the isolated statuses in arrival order. Format each one by concatenating [, the decimal timestamp, the literal s] , and the message; for example, [23s] foo.
Function
showIsolatedMessages(timestamps: int[], messages: String[]) → String[]Examples
Example 1
timestamps = [1,5,12,23]messages = ["foo","foo","foo","foo"]return = ["[23s] foo"]The occurrences at 1 and 5 are within 4 seconds, while those at 5 and 12 are within 7 seconds, so the first three statuses are suppressed. The occurrence at 23 is 11 seconds after the preceding one and is shown.
Example 2
timestamps = [0,2,9,10,12]messages = ["a","b","a","a","b"]return = ["[2s] b","[12s] b"]All three a statuses belong to a duplicate chain. The two b statuses are exactly 10 seconds apart, so both are isolated.
Example 3
timestamps = [4,4,14]messages = ["ping","ping","ping"]return = ["[14s] ping"]The tied arrivals suppress each other. The final status is exactly 10 seconds later, so it remains isolated.
Constraints
1 <= timestamps.length == messages.length <= 10^50 <= timestamps[i] <= 10^9timestampsis sorted in nondecreasing order.1 <= messages[i].length <= 100- Each message contains printable ASCII characters.
- Message equality is exact and case-sensitive.
More Google Phone Screen questions
- Best Stock Trade with Buy and Sell DaysPHONE SCREEN · Seen Nov 2026
- Word Chain Jumps in a GridPHONE SCREEN · Seen Nov 2026
- Dice-Walk Winning ProbabilityPHONE SCREEN · ONSITE INTERVIEW · Seen Nov 2026
- Lowest Common Ancestor in an N-ary TreePHONE SCREEN · ONSITE INTERVIEW · Seen Nov 2026
- Apartment Housemate PreferencesPHONE SCREEN · Seen Nov 2026
- Price at Query TimestampsPHONE SCREEN · Seen Nov 2026
- Course Schedule Cycle DetectionPHONE SCREEN · ONSITE INTERVIEW · Seen Nov 2026
- Logger Rate Limiter with Every-Arrival HistoryPHONE SCREEN · Seen Nov 2026
- Minimum Total Layover WaitPHONE SCREEN · Seen Nov 2026
- Reach a Destination Through Scheduled FlightsPHONE SCREEN · ONSITE INTERVIEW · Seen Nov 2026
Similar questions at other companies
- Per-Client API Rate LimiterDocker · PHONE SCREEN
- Per-Client Sliding-Window Rate LimiterCVS Health · PHONE SCREEN
- Sliding-Window Rate LimiterUber · PHONE SCREENUber interview questions
- Recent Advertisement Click CountsAmazon · PHONE SCREEN
- Completions API Rate LimiterCursor · PHONE SCREENCursor interview questions
- Sliding-Window Rate LimiterStripe · PHONE SCREEN · ONSITE INTERVIEWStripe interview questions
- Key-Value Store GET and PUT QPSDatabricks · PHONE SCREENDatabricks interview questions
- Rate Limiter with Global and Per-User LimitsOpenAI · ONSITE INTERVIEWOpenAI interview questions
- Per-Client Sliding-Window Rate LimiterGeneral Motors · OA
- Metric Counter with a Fake ClockSnap Inc. · ONSITE INTERVIEWSnap Inc. interview questions
Google interview experiences
- Google L4 SWE Phone Screen: 1 Experience
- Google ML Engineering Manager Onsite: 1 Experience
- Google Experienced SWE First Round and Onsite: 1 Experience
- Google AI Coding Interview and AI OA: 2 Experiences
- Google SWE Intern Interview Results Timeline: 13 Experiences
- Google L4 SWE Phone Screen and Kirkland Onsite: 1 Experience