How should I practice Stream Unique Logs in Timestamp Order?

Start by reading the full statement, solve the visible examples, then compare the pattern against related Google onsite interview problems in FastPrep.

Is Stream Unique Logs in Timestamp Order associated with Google?

FastPrep tags this as a Google onsite interview coding practice problem when the problem catalog has that company and stage context.

Problem · Hash Table

Stream Unique Logs in Timestamp Order

Learn this problem

● Medium

GoogleFULLTIMEONSITE INTERVIEW

See Google hiring insights

Problem statement

Process a finite sequence of log-stream operations from left to right. Each log is a pair containing an integer timestamp and a message.

For an add operation, accept the supplied log only if its message has never been accepted earlier in the sequence. A message remains accepted for uniqueness purposes even after its log is returned. Otherwise, ignore the log.
For a get operation, remove and return the currently pending accepted log with the smallest timestamp. If multiple pending logs have the same timestamp, return the one whose message is lexicographically smaller. If no log is pending, return EMPTY.

Only add operations already processed are available to a get. A later operation never changes a result that was already returned.

Return one string for each get, in operation order. Encode a returned log as timestamp|message. The timestamp and message entries at a get position are placeholders and are ignored.

Function

processUniqueLogs(operations: String[], timestamps: int[], messages: String[]) → String[]

Examples

Example 1

operations = ["add","add","get","add","get","get"]timestamps = [5,3,0,1,0,0]messages = ["alpha","beta","","alpha","",""]return = ["3|beta","5|alpha","EMPTY"]

The first get returns 3|beta. The second alpha log is rejected because that message was already accepted, so the next result is 5|alpha. The final get finds no pending log.

Example 2

operations = ["add","add","get","get"]timestamps = [7,7,0,0]messages = ["zeta","alpha","",""]return = ["7|alpha","7|zeta"]

Both logs have timestamp 7, so the lexicographically smaller message alpha is returned first.

Example 3

operations = ["add","get","add","get"]timestamps = [10,0,1,0]messages = ["late","","early",""]return = ["10|late","1|early"]

The first get can see only the first log. The later log has a smaller timestamp, but it does not revise the earlier result.

Constraints

1 <= operations.length <= 10^5.
operations.length == timestamps.length == messages.length.
Every operation is either add or get.
At an add position, 0 <= timestamps[i] <= 10^9.
At an add position, messages[i] contains between 1 and 20 lowercase English letters.
At a get position, timestamps[i] and messages[i] are ignored.