Build Prefix Lookup with a Trie
Company: Google
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
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.
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.
Input: {"words":["a","aa"],"queries":[""]}
Expected Output: [["a","aa"]]
Explanation: Empty prefix.
Input: {"words":["b","a"],"queries":["a","b"]}
Expected Output: [["a"],["b"]]
Explanation: Sorted.
Input: {"words":["same","same"],"queries":["sa"]}
Expected Output: [["same","same"]]
Explanation: Duplicates.
Input: {"words":["abc"],"queries":["x"]}
Expected Output: [[]]
Explanation: No match.
Input: {"words":["apple","app","ape"],"queries":["ap","app"]}
Expected Output: [["ape","app","apple"],["app","apple"]]
Explanation: Multiple prefixes.
Input: {"words":["A","a"],"queries":["a"]}
Expected Output: [["a"]]
Explanation: Case sensitive.