Build a Dynamic Exact-Suffix Search Index
Company: Anduril
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
# Build a Dynamic Exact-Suffix Search Index
Design a data structure with two operations:
- `add(word)` inserts a word into the index.
- `search(suffix)` returns whether at least one inserted word ends with `suffix`.
Search is exact and case-sensitive. Words are added over time, and every search must reflect all preceding additions. For deterministic behavior, repeated insertion of the same word may be treated as idempotent because it does not change a Boolean search result.
### Constraints & Assumptions
- A query matches only at the end of a complete inserted word.
- The data structure must support interleaved additions and searches; rebuilding the entire index after every addition is not acceptable.
- Explain how the total number of stored characters affects memory use.
### Clarifying Questions to Ask
- Is an empty suffix a valid query, and if so should it match whenever the index contains a word?
- Must the index distinguish duplicate insertions or only answer existence queries?
- Is matching case-sensitive, and what character set must the implementation support?
```hint Reverse the direction
A suffix in the original word becomes a prefix after the characters are reversed.
```
```hint A suffix need not be a complete stored word
After reversing, successfully traversing every query character is enough. The path may continue because a longer inserted word can share that suffix.
```
### Evaluation Criteria
- A reversed-trie or equivalent incremental suffix-index design.
- Correct answers for suffixes shared by many words and suffixes equal to a complete word.
- Addition and search time proportional to the respective word or suffix length.
- Memory complexity tied to the number of distinct stored trie nodes.
### Extensions to Discuss
- How would you connect suffix search to a typeahead API without allowing stale HTTP responses to overwrite newer results?
- Where would you debounce requests, and how would you cancel or ignore superseded requests?
- How would the search API prevent SQL injection if part of the implementation queries a relational database?
Quick Answer: Build a dynamic index that answers whether any inserted word ends with an exact, case-sensitive suffix. Use a reversed trie to support interleaved additions and searches in time proportional to word or suffix length, with memory tied to distinct nodes.
Implement dynamic_suffix_search(operations, values). The aligned lists describe interleaved add and search operations. add inserts its value as a word. search appends whether any word added earlier ends with its exact, case-sensitive value. Repeated additions are idempotent. An empty suffix matches exactly when at least one word has been added.
Constraints
- 0 <= operations.length = values.length <= 10.
- Each operation is exactly "add" or "search".
- Added words contain 1 through 50 ASCII English letters.
- Search suffixes contain 0 through 50 ASCII English letters.
- Matching is exact and case-sensitive, and each search sees all preceding additions.
Examples
Input: ([], [])
Expected Output: []
Explanation: No search operations produce no answers.
Input: (['search'], [''])
Expected Output: [False]
Explanation: The empty suffix does not match before any word is added.
Hints
- Reversing a word turns each of its suffixes into a prefix path.
- A successful traversal of every reversed suffix character is enough even if the trie path continues.
- Handle an empty suffix separately by tracking whether any word has been inserted.