Skip to content
MediumTrieAI interview only

Implement Trie (Prefix Tree)

Asked atgoogleamazonmicrosoftmetauberoraclebloomberg

01 · Problem

A trie (pronounced "try") or prefix tree is a tree data structure used to efficiently store and retrieve keys in a dataset of strings. There are various applications of this data structure, such as autocomplete and spellchecker.

Implement the Trie class:

  • Trie() — Initializes the trie object.
  • void insert(String word) — Inserts the string word into the trie.
  • boolean search(String word) — Returns true if the string word is in the trie (i.e., was inserted before), and false otherwise.
  • boolean startsWith(String prefix) — Returns true if there is a previously inserted string word that has the prefix prefix, and false otherwise.

02 · Examples

Example 01
Input
["Trie", "insert", "search", "search", "startsWith", "insert", "search"]
[[], ["apple"], ["apple"], ["app"], ["app"], ["app"], ["app"]]
Output
[null, null, true, false, true, null, true]

After inserting "apple", searching for "apple" returns true but "app" returns false since it wasn't inserted. startsWith("app") returns true because "apple" has prefix "app". After inserting "app", searching for "app" returns true.

03 · Constraints

  • 011 <= word.length, prefix.length <= 2000
  • 02word and prefix consist only of lowercase English letters
  • 03At most 3 * 104 calls in total will be made to insert, search, and startsWith

04 · Optimal complexity

Time
O(m) per operation, where m is the word/prefix length
Space
O(n * m) total, where n is the number of words inserted
05 · Two ways to work on it

Practice it alone or rehearse it as an interview.

Practice Mode gives you an editor and test runs, nothing else. AI Interview Mode puts a voice interviewer on the other side, adds a clock, and ends with a scored summary of the round.

Start a voice interview on this problem