Design lexicographic range query word store
Company: Google
Role: Software Engineer
Category: System Design
Difficulty: hard
Interview Round: Onsite
Design a storage/data structure for a set of strings that supports lexicographic range queries.
You are given a collection of words (strings), stored persistently. For a query range `[L, R]` (inclusive), return **all words `w` such that `L <= w <= R` in lexicographic (dictionary) order**.
Example dataset: `{ "aa", "aaa", "ac", "f", "z" }`
Expected behavior:
- Query `["a", "b"]` → `{ "aa", "aaa", "ac" }`
- Query `["a", "aa"]` → `{ "aa" }`
- Query `["b", "z"]` → `{ "f", "z" }`
- Query `["ab", "b"]` → `{ "ac" }`
Describe the data layout and indexing strategy, and explain how queries are executed efficiently. (Optionally discuss support for inserts/deletes and large-scale storage.)
Overview: This question evaluates competency in designing persistent string storage and lexicographic indexing, covering data structures, indexing strategies, and query execution within the System Design category and requiring practical application of storage layout and access patterns alongside conceptual understanding of ordering and range semantics.