Search Words and Phrases in a Large Line-Oriented File
ConfluentSoftware Engineer · Onsite
Last updated
Design word and exact-phrase search over a line-oriented file that may be much larger than memory. Compare a streaming one-off scan with a persistent positional inverted index, defining tokenization, Unicode and punctuation behavior, file-version binding, updates, result locations, and resource trade-offs.
Search Words and Phrases in a Large Line-Oriented File
A text file contains one sentence per line and may be much larger than memory. Design an API that first supports finding every line containing a word and then supports finding every line containing an exact multiword phrase.
Discuss both a one-off search and a system that serves repeated queries against a mostly stable file. Define tokenization, phrase boundaries, case handling, result format, and how updates become searchable.
Constraints & Assumptions
- Sequential reads are allowed; loading the complete file into memory is not.
- Results identify at least the line number and may include byte offsets.
- Exact behavior for punctuation and Unicode must be stated.
- The repeated-query design may use persistent auxiliary storage.
Clarifying Questions to Ask
- Is a word matched as a token or as an arbitrary substring?
- Must phrase terms be adjacent and in the same line?
- Are queries rare enough for a full scan, or is low query latency required?
- Can the source file be appended to or rewritten while indexing?
Follow-up questions
- How would you return matches in relevance order rather than file order?
- How would you shard an index that no longer fits on one machine?
- What changes for compressed input?
- How can a new index version become visible atomically?
Solution walkthrough is for members
Get the full walkthrough with reference code and complexity analysis, plus Kitty Coach at 300 messages a day. Hints, the code runner and community answers stay free.