Katkat
Back

Document Search: Exact Word Match, Non-Adjacent Phrase Match and AND/OR Queries

ConfluentSoftware Engineer · Onsite
MediumSoftware EngineerOnsiteSoftware Engineering Fundamentals

Last updated

A progressive coding round that builds search over a collection of documents. It starts with exact whole-word lookup, extends to multi-word queries whose words need not be adjacent, and ends with words combined by AND and OR, testing inverted indexes, set operations and clarifying ambiguous query semantics.

You are given a collection of documents, each with an integer id and its text. Build a search component over them. The interviewer adds requirements one at a time, so expect the queries to grow more complex as you go.

The examples below use this collection:

idtext
1the quick brown fox
2the lazy dog sleeps
3a quick dog chased a lazy fox

Constraints and Clarifications

  • The documents are known up front and many queries follow, so preprocessing them is allowed.
  • A query word matches only a whole word in a document: do does not match dog.
  • Results are lists of document ids in ascending order (an assumption of this version).

Clarifying Questions

  • Is matching case-sensitive, and how should punctuation be treated when text is split into words?
  • Can documents be added, changed or removed between queries?

Part 1 — Documents containing a word

Return every document that contains a given word, as an exact match. For example, fox returns [1, 3] and do returns [].

What This Part Should Cover

  • Splitting text into words, and the exact-match rule
  • A structure built once that answers each word lookup quickly
  • The cost of building it and of each query

Part 2 — Documents containing a phrase whose words need not be adjacent

Given a phrase of several words, return every document that contains the phrase, where the phrase's words do not have to be next to each other in the document. For example, quick fox returns [1, 3], even though in neither document does quick come directly before fox.

Clarifying Questions for this Part

  • Must the words appear in the same order as in the phrase? For lazy dog, the answer is [2, 3] if order does not matter and [2] if it does, because document 3 has lazy only after dog.
  • If a word appears twice in the phrase, must it appear twice in the document?

What This Part Should Cover

  • Combining the per-word results, and an evaluation order that keeps the work small
  • Handling the order-sensitive reading if the interviewer wants it
  • Words that appear in no document, empty phrases, and repeated words

Part 3 — Words combined with AND and OR

A query is now a sequence of words joined by AND or OR, such as fox AND dog or fox OR sleeps. Return every document that satisfies the query. For example, fox AND dog returns [3] and fox OR sleeps returns [1, 2, 3].

Clarifying Questions for this Part

  • Does AND bind more tightly than OR, or is the query read from left to right? fox OR dog AND sleeps returns [1, 2, 3] under the first reading and [2] under the second.
  • Can queries contain parentheses, and what should happen with a malformed query such as fox AND or OR dog?

What This Part Should Cover

  • Parsing and validating the query
  • Mapping operators onto set operations with the agreed precedence
  • The cost of evaluation, and keeping intermediate results small

Hints

Hint 1

Build once, query many times: The same documents serve many queries. Think about what to compute once so that a query does not have to reread every document.

Hint 2

Reuse Part 1: Each word of the phrase already gives you a set of documents. Think about how to combine those sets cheaply, and what extra information you would need if word order turned out to matter.

Hint 3

Agree on how the query reads: Before writing code, settle how a mix of `AND` and `OR` groups, then map each operator onto an operation on sets of documents.

Follow-up questions

  • How would you support exact phrase search, where the words must be adjacent and in order?
  • How would you add parentheses and a `NOT` operator?
  • Documents are added and deleted continuously. How do you keep the index current?
  • The collection grows to hundreds of millions of documents. How do you store the per-word document lists and intersect them efficiently?