Build Prefix Lookup with a Trie
Company: Google
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
Build prefix lookup for repeated queries. Given words and query prefixes, return matching words for each query in lexicographic order.
Implement:
```python
def prefix_lookup(words: list[str], queries: list[str]) -> list[list[str]]:
pass
```
Quick Answer: Practice a Google coding interview problem focused on build prefix lookup with a trie. The prompt emphasizes edge cases, clean implementation, and verifiable test behavior without revealing the solution.
Return lexicographic word matches for each prefix query.
Examples
Input: {"words":["car","cat","dog"],"queries":["ca","d"]}
Expected Output: [["car","cat"],["dog"]]
Explanation: Two queries.
Input: {"words":[],"queries":["a"]}
Expected Output: [[]]
Explanation: No words.