Deduplicate Logs: Keep First
Learn this problem
GoogleFULLTIMEONSITE INTERVIEWProblem statement
You are given log entries in encounter order. The ith entry is the pair (timestamps[i], messages[i]). Two entries are duplicates when their messages are equal.
For each distinct message, keep only its first encountered entry. This means the earliest array position wins, even if a later duplicate has a smaller timestamp.
Sort the retained pairs by timestamp in ascending order. When two retained pairs have the same timestamp, sort them by message in ascending lexicographic order.
Return the sorted pairs as a String[]. Encode each pair as timestamp|message, using the timestamp's ordinary decimal representation.
Function
deduplicateLogsKeepFirst(timestamps: int[], messages: String[]) → String[]Examples
Example 1
timestamps = [30,10,20,15,20]messages = ["cache miss","user login","cache miss","heartbeat","user login"]return = ["10|user login","15|heartbeat","30|cache miss"]The first encountered entries for cache miss, user login, and heartbeat have timestamps 30, 10, and 15. The later duplicates are discarded, even though the later cache miss has a smaller timestamp. Sorting the three retained pairs gives the result.
Example 2
timestamps = [5,5,3,4]messages = ["beta","alpha","beta","gamma"]return = ["4|gamma","5|alpha","5|beta"]The later beta entry is removed. The retained alpha and beta entries both have timestamp 5, so their messages determine their order.
Example 3
timestamps = []messages = []return = []There are no log entries, so there are no retained pairs.
Constraints
timestamps.length == messages.length0 <= timestamps.length <= 200000-10^9 <= timestamps[i] <= 10^91 <= messages[i].length <= 100- Each message contains printable ASCII characters other than
|. - The total length of all messages does not exceed
10^6.