Implement Trie insertion, deletion, and prefix search
Filed under Goldman Sachs
Free read 2 of 3Confirm string character set and whether deletion needs to clean up unused nodes to save memory.
The question
Implement a Trie data structure supporting insertion, deletion, and finding all stored words that start with a given prefix.
Constraints
- Words consist of lowercase English letters
- Operations: insert(word), searchPrefix(prefix), delete(word)
Examples
- Input
- insert("cat"), insert("car"), getWordsWithPrefix("ca")
- Output
- ["cat", "car"]
- Why
- Both words start with the prefix "ca" and are retrieved from the Trie.
Approach
Confirm string character set and whether deletion needs to clean up unused nodes to save memory.
Define a TrieNode class containing a dictionary/array of children and a boolean flag is_end_of_word.
Implement insert by traversing and creating nodes. Implement prefix search by navigating to the prefix node and collecting all descendant words via DFS.
Handle deletion recursively to safely remove nodes bottom-up only if they have no other children and are not endpoints for other words.
Tips
- What they are testing: Test inserting overlapping words, deleting a word that is a prefix of another, and searching for non-existent prefixes.
- Common mistake: Forgetting to unmark the end-of-word flag during deletion or removing nodes that are shared by other valid words.
Related Goldman Sachs questions
Collected from public candidate posts and coding forums. Updated Nov 2026.