Prefix Autocomplete via Trie

Requirements Create a data structure from a collection of words. Implement find_all_by_prefix(prefix) -> List[str] so it produces every stored word whose beginning matches prefix. The expected interview solution uses a trie; a hashmap containing complete words is acceptable as a baseline approach. Examples Example 1 Input: word list ["car", "cat", "dog"], prefix "ca" Output: ["car", "cat"] Both car and cat begin with ca, while dog does not. Example 2 Input: word list ["app",…