Drop Recent Duplicate Messages
C3.ai● MediumNEW GRADOAProblem statement
Process a stream of messages and drop recent duplicates. Event i has timestamp timestamps[i] and text messages[i]; timestamps are in nondecreasing order.
For this exercise, two messages are duplicates exactly when their text is equal, including case and whitespace. Accept the first occurrence of each text. Accept a later occurrence only when at least window time units have elapsed since the most recent accepted occurrence of that same text. Otherwise, drop it. Dropped occurrences do not change the last accepted timestamp.
Process events in input order, including events with equal timestamps. Return a boolean array whose element i is true if event i is accepted and false if it is dropped. An empty stream returns an empty array.
Function
keepMessages(timestamps: int[], messages: String[], window: int) → boolean[]Examples
Example 1
timestamps = [1,2,3,8,9]messages = ["a","b","a","b","a"]window = 7return = [true,true,false,false,true]The event at time 3 repeats the accepted a from time 1. At time 8, b is only 6 units after its last accepted occurrence. At time 9, a is eligible.
Example 2
timestamps = [0,3,7]messages = ["x","x","x"]window = 5return = [true,false,true]The dropped event at time 3 does not restart the interval. Seven units have elapsed since the accepted event at time 0.
Example 3
timestamps = []messages = []window = 2return = []No messages require a decision.
Constraints
0 <= timestamps.length = messages.length <= 10^5.0 <= timestamps[i] <= 10^9, in nondecreasing order.1 <= window <= 10^9.- Each message contains at most 100 ASCII characters; empty text is allowed.