Deduplicate Logs: Keep Latest
Learn this problem
GoogleFULLTIMEONSITE INTERVIEWProblem statement
You are given log entries. The ith entry is the pair (timestamps[i], messages[i]). Two entries are duplicates when their messages are equal.
For each distinct message, keep one entry whose timestamp is greatest among all entries with that message. If that greatest timestamp occurs more than once for the same message, those entries represent the same retained pair and still produce only one result.
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
deduplicateLogsKeepLatest(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 = ["15|heartbeat","20|user login","30|cache miss"]The greatest timestamps for cache miss, user login, and heartbeat are 30, 20, and 15. Sorting those retained pairs by timestamp gives the result.
Example 2
timestamps = [5,5,9,9,5]messages = ["beta","alpha","beta","alpha","gamma"]return = ["5|gamma","9|alpha","9|beta"]The latest alpha and beta pairs both have timestamp 9, so their messages determine their order after gamma.
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.