Grokking the Coding Interview: Patterns for Coding Questions
Vote

0% completed

​

Implement Trie (Prefix Tree) (medium)

Problem Statement

Design and implement a Trie (also known as a Prefix Tree). A trie is a tree-like data structure that stores a dynamic set of strings, and is particularly useful for searching for words with a given prefix.

Implement the Solution class:

  • Solution() Initializes the object.
  • void insert(word) Inserts word into the trie, making it available for future searches.
  • bool search(word) Checks if the word exists in the trie.
  • bool startsWith(word) Checks if any word in the trie starts with the given prefix.

Examples

  1. Example 1:
    • Input:

.....

.....

.....

Like the course? Get enrolled and start learning!
J

Jimmy

· 2 years ago

In example #3, the trie operations should be:

["Trie", "insert", "search", "startsWith", "startsWith"]

instead of:

["Trie", "insert", "search", "search", "startsWith"]

"grap" is not a valid word in the trie.

J

jmezzbmxer

· 2 years ago

Should startsWith not be checking to ensure there are children present, rather than simply excluding an isEnd check when comparing it to the search function?

This may be an issue of semantics, but if you had a test case which consists of the following;

['Trie', 'insert('app')', 'startsWith('app')']

Does the word "app" really have a prefix of app? I would think a prefix can not be a word on it's own, so despite us not checking if it's the end of a word the provided solution is not checking if it's actually a prefix of a word. The current solution would return True to that startsWith call.

Adding an additional check like the following would be ensuring this is an actual prefix rather than a full word. This would only be adding O(1) to the time complexity (essentially a loop with a maximu