Skip to content

Topic 12 of 20

Tries

Prefix trees for autocomplete, dictionary search and bitwise XOR tricks.

10 problems0 Easy8 Medium2 Hard

The concept

A trie (prefix tree) stores strings character by character, so all words that share a prefix share a path from the root. Inserting or searching a word of length L costs O(L), no matter how many words are stored, and "does any word start with this prefix?" is answered by simply walking down the tree. That makes tries the natural structure for autocomplete, spell-checking and dictionary problems.

Each node typically holds a map (or a fixed array of 26) of children plus an isEnd flag. Beyond basic insert and search, the interview patterns are: wildcard search (DFS over all children when you see a '.'), trie + backtracking (search a whole board for many words at once, pruning as soon as a prefix is missing), and the bitwise trie, which stores numbers bit by bit to find the maximum XOR pair in O(n · 32).

This is a short topic, but tries show up regularly at Google, Amazon and Microsoft, often as the optimisation that turns a timed-out brute force into an accepted solution.

Patterns you will learn

Problems, in order

  1. 1

    Build the data structure from scratch; asked verbatim in interviews.

    Prefix TreeReported at: AmazonGoogleMicrosoft+6
  2. 2

    Wildcard search with DFS over children.

  3. 3

    Shortest-prefix lookup for every word.

    Prefix TreeReported at: Meta
  4. 4

    Building words one letter at a time through the trie.

    Trie + DFSReported at: Google
  5. 5

    Storing aggregate values on trie nodes.

    Prefix Tree with AggregatesReported at: Google
  6. 6

    DFS that allows exactly one mismatch.

    Trie + DFS (One Mismatch)Reported at: MetaGoogle
  7. 7

    Autocomplete, the textbook trie application.

    Prefix Tree / Sort + Binary SearchReported at: AmazonGoogleMeta+3
  8. 8

    The bitwise trie for greedy XOR maximisation.

    Bitwise TrieReported at: BloombergAdobe
  9. 9

    Trie-pruned grid backtracking; a top Hard at Google and Amazon.

    Trie + BacktrackingReported at: AmazonMicrosoftGoogle+6
  10. 10

    Prefix and suffix reasoning across a word list.

    Trie / Hash Map of Reversed WordsReported at: GoogleAppleMeta+2