Query Log Match
Problem statement
You are given a finite array stream containing query registrations, log events and query deletions. Process the events from left to right.
Q:introduces a query payload.L:introduces a log payload.D:introduces a query ID to delete.
For query and log payloads, tokenize maximal contiguous ASCII letter-or-digit sequences and lowercase the tokens. Punctuation and whitespace separate tokens. Repeated tokens within one payload count once.
An active query matches a log when every distinct query token occurs as an exact token in the log. Token order does not matter; fail does not match failed.
- For each query, assign the next 1-based ID, even if its payload duplicates an earlier query. IDs increase on registrations only and are never reused. Activate the query and append
ACK: <payload>; ID=<id>. - For each log, find all previously registered queries that are still active and match it. Order their IDs increasingly. If any match, append
M: <payload>; Q=<id1>,<id2>,...; otherwise append nothing. - For a deletion, deactivate that registered ID. Deleting an unknown or already deleted ID is a no-op. Append no message. An unknown deletion does not reserve or affect a future registration ID.
Query and log payloads in returned messages preserve their original spelling, capitalization, spacing and punctuation. A deletion affects later logs only; it never changes a previously appended message. Return appended messages in event order.
Function
processLiveTail(stream: String[]) → String[]Examples
Example 1
stream = ["Q: database","Q: Stacktrace","Q: loading failed","L: Database service started","Q: snapshot loading","Q: fail","L: Started processing events","L: Loading main DB snapshot","L: Loading snapshot failed no stacktrace available"]return = ["ACK: database; ID=1","ACK: Stacktrace; ID=2","ACK: loading failed; ID=3","M: Database service started; Q=1","ACK: snapshot loading; ID=4","ACK: fail; ID=5","M: Loading main DB snapshot; Q=4","M: Loading snapshot failed no stacktrace available; Q=2,3,4"]The query snapshot loading matches Loading main DB snapshot because both exact tokens occur, even though their order is reversed. The token fail does not match failed. The unmatched log Started processing events produces no message.
Example 2
stream = ["Q: Error, timeout!","Q: timeout error","Q: error error","L: timeout... ERROR?","Q: timeout error","L: error only","L: Timeout/error"]return = ["ACK: Error, timeout!; ID=1","ACK: timeout error; ID=2","ACK: error error; ID=3","M: timeout... ERROR?; Q=1,2,3","ACK: timeout error; ID=4","M: error only; Q=3","M: Timeout/error; Q=1,2,3,4"]Punctuation separates tokens, matching is case-insensitive, and repeated query tokens count once. Identical query token sets still receive distinct IDs, so the last log reports both IDs 2 and 4.
Example 3
stream = ["L: alpha beta","Q: alpha","L: beta alpha","Q: beta","L: alpha beta"]return = ["ACK: alpha; ID=1","M: beta alpha; Q=1","ACK: beta; ID=2","M: alpha beta; Q=1,2"]The first log has no previously registered queries, so it produces no message. Later query registrations do not change earlier results.
Example 4
stream = ["Q: error","Q: error timeout","L: Error timeout","D: 1","L: error timeout","D: 2","L: error timeout","Q: error","L: error"]return = ["ACK: error; ID=1","ACK: error timeout; ID=2","M: Error timeout; Q=1,2","M: error timeout; Q=2","ACK: error; ID=3","M: error; Q=3"]The first log matches queries 1 and 2. Deleting 1 leaves only query 2 for the next log. Deleting 2 leaves no active query, so the following log emits nothing. The next registration receives ID 3, and the final log matches it. Deletions emit no messages.
Constraints
1 <= stream.length <= 200004 <= stream[i].length <= 200000- The total length of all event strings is at most 200000.
- Every event contains only printable ASCII characters.
- Every event starts with exactly
Q:,L:, orD:. A Q/L payload contains at least one ASCII letter or digit. A D payload is a decimal integer from 1 through 1000000000, with no leading zero, spaces or other characters. - The sum of the lengths of all returned message strings is at most 200000.