AI InterviewSearch…Search problems, topics, or pages…Ctrl KGet started

Topic

Trie coding problems

A trie, or prefix tree, stores a set of words one character per level, so words that share a prefix share the path that spells it.

New to trie? Read the Trie (Prefix Tree) tutorial first.

27 problems · 1 easy · 16 medium · 10 hard · judged by hidden tests in 13 languages

27problems

1 easy

16 medium

10 hard

Sign in to tick off what you solve.

Study plan: 11 problems · about 7 h 10 min

Start the study plan

Next up: Maximum Strong Pair XOR I

How it works

Trie, step by step

Prefix search over words, with a trie

insert "car", "cat", "cart", "dog"; find words starting with "ca"

rootwords"car""cat""cart""dog"

A trie stores words letter by letter along paths from the root, so words with the same beginning share their first nodes. Each node also records whether a word ends there, because a word can be the prefix of a longer one.

0:01 / 0:28Step 1 of 7
Transcript · 7 steps

Study plan

Learn trie in 7 days

11 of the 27 Trie problems (1 easy, 7 medium and 3 hard) over 7 days, about 7 h 10 min in all — the pattern first, then easiest to hardest. After that, the other 16 in the full list below are practice at your own pace. Then move on to Backtracking.

  1. Day 1

    about 1 h 10 min

    Learn the pattern: read the essentials and step through the walkthrough above, then solve these 2.

  2. Day 2

    about 1 h 10 min

    More mediums. Before coding each one, write down what state the pattern keeps and when it changes.

  3. Day 3

    about 1 h 10 min

    More mediums. Before coding each one, write down what state the pattern keeps and when it changes.

  4. Day 4

    about 1 h 10 min

    More mediums. Before coding each one, write down what state the pattern keeps and when it changes.

  5. Day 5

    about 50 min

    Hard problems: the pattern combined with a second idea. Give each a full attempt before reading the editorial.

  6. Day 6

    about 50 min

    Another hard one. If it beats you after a real attempt, read the editorial, then solve it again tomorrow from memory.

  7. Day 7

    about 50 min

    Another hard one. If it beats you after a real attempt, read the editorial, then solve it again tomorrow from memory.

    Next topic: Backtracking

Trie Coding Problems: 27 Questions with Solutions

27 trie coding problems — 1 easy · 16 medium · 10 hard — with solutions in 13 languages. Plus a step-by-step walkthrough and a 7-day plan.

  • Problems: 27
  • By difficulty: 1 easy · 16 medium · 10 hard
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
  • Cost: Free on every plan; sign in to run and submit

A trie, or prefix tree, stores a set of words one character per level, so words that share a prefix share the path that spells it. Asking whether any stored word starts with a given prefix, or which stored word is the shortest prefix of another, then costs the length of the word rather than the size of the dictionary. The same tree built over the bits of integers, highest bit first, answers maximum-XOR questions greedily. The problems here practise building the tree, marking where words end, and walking it alongside a second string.

New to trie? Read the Trie (Prefix Tree) tutorial first.

How trie works, step by step

carttdogrootcarcatcartdogwords"car""cat""cart""dog"prefix "ca"→ car, cart, cat
Prefix search over words, with a trie. Example: insert "car", "cat", "cart", "dog"; find words starting with "ca"
  1. A trie stores words letter by letter along paths from the root, so words with the same beginning share their first nodes. Each node also records whether a word ends there, because a word can be the prefix of a longer one.
  2. Insert "car": the trie is empty, so c, a and r become a chain of new nodes from the root, and r is marked as the end of a word.
  3. Insert "cat": the walk reuses c and a from "car", since they share the prefix "ca", then adds t and marks it as the end of a word.
  4. Insert "cart": c, a and r already exist, because "car" is a prefix of "cart", so only t is new, hung below r. r keeps its own end mark, so "car" and "cart" are both words.
  5. Insert "dog": no stored word starts with d, so d, o and g are all new, a separate branch from the root, and g is marked as an end. A trie only shares what words really have in common.
  6. To find the words starting with "ca", walk from the root: c, then a, 2 steps however many words are stored. That node has no end mark, so "ca" is not a word itself, but everything below it starts with "ca".
  7. Collecting every end mark below that node gives "car", "cart" and "cat", and the "d" branch is never touched. Inserting or walking a word of length L costs O(L); listing the matches costs the size of that one subtree.

Trie study plan

11 of the 27 Trie problems (1 easy, 7 medium and 3 hard) over 7 days, about 7 h 10 min in all — the pattern first, then easiest to hardest. After that, the other 16 in the full list below are practice at your own pace. Then move on to Backtracking.

Day 1

Learn the pattern: read the essentials and step through the walkthrough above, then solve these 2.

Day 2

More mediums. Before coding each one, write down what state the pattern keeps and when it changes.

Day 3

More mediums. Before coding each one, write down what state the pattern keeps and when it changes.

Day 4

More mediums. Before coding each one, write down what state the pattern keeps and when it changes.

Day 5

Hard problems: the pattern combined with a second idea. Give each a full attempt before reading the editorial.

Day 6

Another hard one. If it beats you after a real attempt, read the editorial, then solve it again tomorrow from memory.

Day 7

Another hard one. If it beats you after a real attempt, read the editorial, then solve it again tomorrow from memory.

Next topic: Backtracking

Trie: the essentials

When to reach for it

Many words and questions about their prefixes: does any stored word start with this, which root is the shortest prefix of this word, is every prefix of a word also a word. A whole-word lookup is a Hash Table job. Built over bits, highest first, a trie also finds the largest XOR of two numbers.

The pattern

Each node maps a character to a child and flags where a word ends. Insert walks the word, creating missing children, and flags the last node; search walks the same way and fails at the first missing child. Every node passed spells a prefix of the word, so the first flagged one is its shortest stored prefix.

def insert(trie, word):
    node = trie
    for ch in word:
        node = node.setdefault(ch, {})  # the child, created if missing
    node["$"] = True                    # a word ends here

def shortest_root(trie, word):          # shortest stored prefix, or None
    node = trie
    for i, ch in enumerate(word):
        node = node.get(ch, {})         # {} once the path runs out
        if "$" in node: return word[:i + 1]
    return None

Cost

O(L) per insert or search for a word of length L, however many words are stored, and at most one node per character inserted. A 26-slot array per node is faster than a dictionary and far larger.

Common mistakes

  • Taking a path for a word: "app" lies on the path of "apple" but is stored only if its node is flagged.
  • Checking the flag only at the end of the word, which misses every shorter root.
  • 26-slot arrays for 10⁵ words of length 100: up to 2.6 × 10⁸ slots.
  • Building a bit trie lowest bit first, when the highest differing bit decides an XOR.

Start with

All trie problems

Easy (1)

Medium (16)

Hard (10)

Companies that ask trie problems

Next topic: Backtracking