Katkat
Back

Machine Coding: Word Search and Ordered Phrase Search Across a List of Documents

ConfluentSoftware Engineer · Onsite
MediumSoftware EngineerOnsiteSoftware Engineering Fundamentals

Last updated

A machine-coding exercise that asks you to build a search component over a list of text documents, first finding the documents that contain a given word and then those where a phrase's words appear in the same sequence. It tests tokenization choices, index design, and handling of repeated words and edge cases.

In a machine-coding round you are given a list of documents, where each document is a string of text identified by its position in the list. Build a small, well-structured search component over the list and implement two queries, in order.

Clarifying Questions

  • What counts as a word: is matching case-insensitive, and how should punctuation and other separators be handled?
  • What should a query return: the matching document ids only, or also the positions or number of matches, and in what order?
  • Is the document list fixed once the component is built, or can documents be added or removed later?
  • Roughly how many documents and how much total text are there, and how often is each kind of query run?

Part 1 — Find a word

Implement find_word(word), which returns the documents that contain the given word as a whole word. State the time and space cost of preparing the component and of each query.

What This Part Should Cover

  • One tokenization rule, applied identically to documents and to queries, that matches whole words rather than substrings
  • The precomputed structure that maps a word to the documents containing it, and its build cost
  • Query cost, result ordering, and behavior for a word that appears nowhere

Part 2 — Find a phrase

Implement find_phrase(phrase), which returns the documents in which the words of the phrase appear in the same sequence as in the phrase.

Clarifying Questions for this Part

  • Must the phrase's words be adjacent in the document, or only appear in the same order with other words allowed between them?
  • Can a phrase repeat a word, as in "to be or not to be", and must a match stay inside one sentence?

What This Part Should Cover

  • The extra per-occurrence information the index keeps, and how a candidate document is verified against the phrase
  • How candidate documents are narrowed before verification
  • Correctness with repeated words, and the cost of a phrase query

Hints

Hint 1

Pay once: If the same document list is searched many times, think about what to precompute so that a query does not have to read every document again.

Hint 2

What the word lookup loses: A document can contain every word of the phrase without containing the phrase. Think about what to record for each occurrence of a word so that order can be checked without rescanning the text.

Follow-up questions

  • How would you support adding and deleting documents after the index has been built?
  • How would you rank matching documents, for example by how often the phrase occurs?
  • If the index no longer fits in one machine's memory, how would you partition it, and what does a phrase query then cost?
  • How would you change Part 2 to find documents where the words appear within `k` positions of each other?