โ† Goldman Sachs questions

Implement Trie insertion, deletion, and prefix search

Filed under Goldman Sachs

Free read 2 of 3

Confirm 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

  1. Confirm string character set and whether deletion needs to clean up unused nodes to save memory.

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.