Trie (Prefix Tree) Implementation

I would start by defining a TrieNode class containing a dictionary for children and a boolean flag indicating if a word ends here. For Google's scale, I'd prefer a hash map for children to handle dynamic character sets efficiently, though an array of size 26 works well for standard ASCII. During insertion, I iterate through each character of the input string. If a child node for that character doesn't exist, I create one. I move down the tree until the end, then set the isEnd flag to true. This ensures we don't duplicate storage for common prefixes. For searching, I traverse the tree following the characters. If I hit a null pointer before finishing the string, the word isn't present. For startsWith, the logic is identical, but I simply return true if I successfully reach the last character without needing the isEnd flag. This operation runs in O(K) time, where K is the key length, making it significantly faster than scanning a list of strings. Space complexity is proportional to the total number of unique characters across all inserted words. While this uses more memory than a simple hash set, it is indispensable for real-time autocomplete systems where partial matches are critical. I would also consider adding a counter field to track how many times a word was inserted, which is useful for ranking suggestions.