Quick Overview

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.

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.

Overview: 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

  1. Index each query by its set of distinct words and store the required count per query.
  2. Build an inverted index: word -> list of query IDs containing that word.
  3. 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.

Loading coding console...

Show the approach

Approach

Maintain an inverted index from word to the list of query IDs that contain it, and track for each query the number of distinct words it requires. When a log arrives, convert its words to a set to ignore repeats, then for each word, increment a counter for every query that includes that word. A query matches the log exactly when the number of its distinct words seen equals its required count. Output the matched queries in arrival order by sorting their IDs.

Time complexity:
Building the index over all queries is O(total distinct query words). For a log with U distinct words, time is O(sum over its words of postings size) to count, plus O(K log K) to output K matches in arrival order.
Space complexity:
O(Q + P), where Q is the number of queries (to store texts and counts) and P is the total size of the inverted index postings across all words.