Query / Log Stream Matching

DatadogPhone screenMedium

You process a stream of messages in order. Each message registers a query or is a log line, and each message produces zero or one output line.

Part 1: Match queries against log lines

You are given a list of message strings livetail_stream, processed in order. Return the list of output lines.

Each message is one of:

"Q: <words>" registers a query. Queries get IDs 1, 2, 3, ... in the order they arrive. Output "ACK: <words>; ID=<id>".
"L: <line>" is a log line. Output "M: <line>; Q=<ids>", where <ids> lists, in increasing order and comma-separated, the IDs of every query registered so far whose words all appear in the line. If no query matches, output nothing for that line.

Matching rules:

Words are separated by spaces. Matching is case-insensitive: "Database" matches "database".
A word matches only a whole word: "fail" does not match "failed".
Word order does not matter: the query "snapshot loading" matches the line "Loading main DB snapshot".
A query matches only log lines that arrive after it.

Example 1

livetail_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"]
Output: ["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"]

Why: Query 1 matches the first log line. The last line contains stacktrace (query 2), loading and failed (query 3), and snapshot (query 4); query 5 (fail) does not match because failed is a different whole word. Started processing events matches no query, so it produces no output.

Constraints

1 <= len(livetail_stream) <= 1000
each message in livetail_stream starts with "Q: " or "L: "
no message in livetail_stream has leading, trailing, or consecutive spaces
every "Q: " message in livetail_stream has at least one word after the "Q: " prefix

Practice this question

Import your own questions

Paste a question you were asked and get a full problem: statement, tests and a checked solution.

Import a question