Add and Search Word - Data structure design
Design a data structure that supports adding new words and finding if a string matches any previously added string. The search query can contain the dot '.' character to represent any one letter.
Why Interviewers Ask This
Google asks this to evaluate your ability to balance time and space complexity when designing data structures. They specifically test if you can implement a Trie (prefix tree) that handles wildcard searches efficiently, rather than using simple linear scans which fail at scale.
How to Answer This Question
1. Clarify requirements: Confirm the '.' wildcard behavior matches exactly one character and ask about case sensitivity or input constraints.
2. Propose the core structure: Suggest a Trie where each node contains a map of children characters and a boolean flag indicating word completion.
3. Detail the add operation: Explain how to traverse or create nodes for each character in O(L) time, where L is word length.
4. Design the search logic: Describe a recursive depth-first search function. For regular characters, move to the specific child; for '.', iterate through all valid children recursively.
5. Optimize and analyze: Discuss time complexity O(N*M) for search versus O(M) for add, and address edge cases like empty strings or invalid inputs before coding.
Key Points to Cover
- Explicitly choosing a Trie over a hash set due to the wildcard requirement
- Demonstrating a recursive backtracking strategy for handling the dot wildcard
- Clearly defining time complexity differences between insertion and search operations
- Handling edge cases like null inputs or mismatched lengths gracefully
- Writing clean, modular code that separates logic for adding and searching
Sample Answer
To solve this, I would design a custom Trie data structure. First, I define a Node class containing a dictionary for children and a boolean 'isEndOfWord'.
For the addWord method, we iterate through the string. If a char…
Common Mistakes to Avoid
- Using a simple list or array scan which results in O(N*L) search time instead of optimized traversal
- Attempting to generate all possible combinations for dots which causes exponential blowup
- Forgetting to mark the final node as a complete word during insertion
- Ignoring base cases in recursion leading to stack overflow errors on deep trees
Sound confident on this question in 5 minutes
Answer once and get a 30-second AI critique of your structure, content, and delivery. First attempt is free — no signup needed.