Match logs to prior queries
Company: Datadog
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
##### Question
You receive a stream of strings, each beginning with either "Q:" (query) or "L:" (log). A query consists of space-separated words and should be indexed when it arrives. For every subsequent log line, output all previously seen queries for which every word in the query appears at least once in the log (case-sensitive, word boundaries by space). Design and implement an efficient algorithm/data structure to support this online matching and output.
Quick Answer: This question evaluates understanding of streaming algorithms, string indexing, and set-based matching, focusing on designing efficient online data structures to match stored queries against incoming logs within the Coding & Algorithms domain.
You receive a list of lines, each beginning with either "Q:" (query) or "L:" (log). A query line has space-separated words and is indexed when it appears. For every subsequent log line, output all previously seen queries for which every distinct word in the query appears at least once in the log. Matching is case-sensitive and words are split by spaces. Return, for each log line in input order, the list of matching queries in the order the queries were received. Duplicate query strings are treated as distinct entries.
Constraints
- 1 <= len(lines) <= 200000
- Each line starts with exactly "Q: " or "L: "
- Each query and log contains at least one word after the prefix
- Words are separated by single spaces and contain no spaces themselves
- Matching is case-sensitive
- Let T be the total number of words across all lines; T <= 2,000,000
Hints
- Index each query by its set of distinct words and store the required count per query.
- Build an inverted index: word -> list of query IDs containing that word.
- For each log, take its distinct words and accumulate counts per candidate query ID using the inverted index; a query matches if its seen count equals its required count.