Datadog Software Engineer Interview Experience — Matching Queries Against a Log Stream

The first-round problem was query and log stream matching. I was given a stream containing two message types:

• Q: xxx was a query. Each query needed a unique ID, and I had to output an acknowledgment.
• L: xxx was a log. For each log, I had to output the IDs of all queries that it completely matched.

The example input was:

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"
]

The expected output was:

livetail_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"
]

My approach was to use a HashMap<String, List<Integer>> that mapped every word in a query to the corresponding query IDs. While processing a log, I would look up the query IDs associated with each word and maintain a counter for how many words from each query had matched. When a counter equaled the number of words in that query, the query was fully matched, so I would add its ID to the result.

I processed the stream in order: on a Q message I emitted the acknowledgment, and on an L message I emitted every fully matched query ID.