How should I practice Query Log Match?

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

Is Query Log Match associated with Datadog?

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

Problem · Array

Query Log Match

Learn this problem

● Medium

DatadogFULLTIMEPHONE SCREENONSITE INTERVIEW

Problem statement

You are given a finite array stream containing query-registration events and log events. Process the events from left to right.

Every event starts with exactly one of these prefixes:

Q: introduces a query payload.
L: introduces a log payload.

Tokenize a payload into its maximal contiguous ASCII letter-or-digit sequences, and convert every token to lowercase. Punctuation and whitespace separate tokens. Repeated tokens within one payload count once.

A registered query matches a log when every distinct token in the query occurs as an exact token in the log. Token order does not matter. A token such as fail does not match failed.

Build the returned messages using these rules:

For every query event, assign the next 1-based ID, even when its payload duplicates an earlier query. Append ACK: <payload>; ID=<id>.
For every log event, find all previously registered matching query IDs and order them increasingly. If at least one query matches, append M: <payload>; Q=<id1>,<id2>,.... If no query matches, append nothing.

The payload in an output message must preserve its original spelling, capitalization, spacing, and punctuation. Return all 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.

Constraints

1 <= stream.length <= 2 * 10^4
The total length of all strings in stream is at most 2 * 10^5.
Every event starts with exactly Q: or L: .
Every payload contains at least one ASCII letter or digit.
Every event contains only printable ASCII characters.