This page needs a newer browser to run its tools. You can still read everything here.

Data Structures & Algorithms (DSA) Module 15

Tries interview questions

Interview questions on tries: short warm-ups, then what each harder question tests, the first step of a good answer and its follow-ups.

8 questions: 3 warm-ups and 5 with model answers · Levels: Fresher to staff

Warm-up questions

Short questions with short answers, each answered in full.

Fresher to mid

How does a trie count the stored words that start with a prefix in O(L) time?

Answered in the lesson Tries: prefix trees for strings
Fresher to mid

When should trie nodes keep an array of children instead of a hash map?

Answered in the lesson Tries: prefix trees for strings
Fresher to mid

Why does a dot wildcard make a trie search slower than an exact search?

Answered in the lesson Trie applications: wildcards, word search, XOR

Questions with model answers

What each question tests, the first step of a good answer and the follow-ups to expect.

Mid to senior

A contacts app suggests names after every key typed. It holds 200,000 names of about 12 characters each. Would you keep them in a trie? Estimate its nodes and its memory in CPython, and compare it with a sorted list searched by binary search.
What it tests

Bounding a trie's nodes by its characters and shared prefixes, estimating bytes per node, and weighing a trie against a sorted list for prefix queries on a list that rarely changes.

First step

Bound the nodes first: at most one per character, 200,000 × 12 = 2.4 million, and fewer where names share their beginnings. Then multiply by the cost of one node; a CPython node with a dict of children took about 206 bytes in the lesson's measurement.
Follow-ups
- How much would a compressed trie save, and what does it cost in code?
- The list changes once a day. Does that change your choice?
- Each key must be answered within a millisecond. Does the sorted list manage that?
From the lesson Tries: prefix trees for strings
Model answer, Pro. Model answers open with any pass; prices are in the notice on this page.
Opening the model answers with your pass…
Model answers open with any MySmartCoPilot pass.
Pro pass · 1 week₹79$2.99
30 days₹179$5.99
1 year₹1,699$45
One payment; a pass never renews. The price shown is the total you pay: no fees or charges are added at checkout.
Passes can’t be bought right now, so the model answers can’t be opened at the moment. If you have a pass, enter your licence key.
Choose a pass I have a licence key
It also opens every other in-depth part in Learn and every Pro tool. Sales are final, except where the law gives you a right to withdraw, for example in the EU and the UK (refund policy).
In the answer:
- Model answer
- Follow-up answers
- Common mistakes
- Rubric
- Variants
- about 3 minutes
Fresher to mid

Your trie keeps a counter on every node of the words that pass through it, so that it can count words by prefix. Design delete(word). What goes wrong if delete only clears the end-of-word flag, and when should nodes be freed?
What it tests

Keeping prefix counters consistent under deletion, handling words that are absent or are prefixes of other words, and freeing nodes that no longer lead to any word.

First step

Check that the word is stored before changing anything: walk down, and if the walk breaks off or the end count of the last node is 0, return without touching a counter. Only then walk again, subtracting 1 from the passing counter of every node on the path and from the end count of the last node.
Follow-ups
- How do you free the nodes that no stored word passes through any more?
- What changes when the deleted word is the start of another stored word, such as pan while pants is stored?
- Does delete still run in O(L) time?
From the lesson Tries: prefix trees for strings
Model answer, Pro.
In the answer:
- Model answer
- Follow-up answers
- Common mistakes
- Rubric
- Variants
- about 3 minutes
Mid to senior

A crossword helper keeps 500,000 words in a trie. Patterns such as cros.... come back at once, but patterns such as ....word, with the dots first, are slow. Explain why with numbers, and propose two changes that make leading dots cheap.
What it tests

Estimating the fan-out of dots from their position and the alphabet, and designing indexes such as a reversed trie or tries per length that keep patterns with leading dots fast.

First step

Count the branches before any letter prunes them. With 26 letters, k leading dots can open up to 26^k paths, limited by the nodes at depth k: four leading dots can touch every four-letter prefix in the dictionary before the first fixed letter cuts anything. Then ask what changes if the walk met the letters first.
Follow-ups
- When does a trie of reversed words not help?
- How much memory do the extra indexes cost?
- Would you also give each word length its own trie?
From the lesson Trie applications: wildcards, word search, XOR
Model answer, Pro.
In the answer:
- Model answer
- Follow-up answers
- Common mistakes
- Rubric
- Variants
- about 3 minutes
Mid to senior

A word game checks a 12 × 12 board against a dictionary of 50,000 words: every word spelled by a chain of side-by-side cells that uses no cell twice. One search per word is too slow. Design a faster search, estimate its work, and say how found words are handled.
What it tests

Combining a trie with backtracking, cutting paths at the first prefix no word has, reporting each word once, pruning finished branches, and estimating the work from the board and the dictionary.

First step

Turn the loops around. Instead of one search per word, start one walk from each of the 144 cells and walk the board and a trie of all the words together, stepping onto a neighbour only when the trie has a child for that neighbour's letter.
Follow-ups
- How do you avoid reporting a word twice?
- What changes if diagonal moves are allowed?
- The same dictionary is checked against thousands of boards. What do you build once?
From the lesson Trie applications: wildcards, word search, XOR
Model answer, Pro.
In the answer:
- Model answer
- Follow-up answers
- Common mistakes
- Rubric
- Variants
- about 3 minutes
Senior to staff

A router holds 900,000 IPv4 routes, each a prefix such as 10.20.0.0/16, and must find the longest matching prefix for every packet's destination. How would a binary trie answer this, how many steps and nodes does it need, and how would you make lookups faster?
What it tests

Longest-prefix matching as a trie walk that remembers the last route seen, bounding its steps and nodes, and multibit and compressed tries as the ways to cut memory accesses.

First step

Store each route at the node its prefix bits reach, with the default route at the root. For a destination, walk its 32 bits from the most significant one, remember the last node that holds a route, and stop at the first missing child: at most 32 steps, whatever the number of routes.
Follow-ups
- How many nodes can 900,000 routes need at most?
- Why must the walk not stop at the first route it passes?
- How would you cut the up to 32 memory accesses of a lookup?
From the lesson Trie applications: wildcards, word search, XOR
Model answer, Pro.
In the answer:
- Model answer
- Follow-up answers
- Common mistakes
- Rubric
- Variants
- about 3 minutes

All Data Structures & Algorithms (DSA) interview questions · The Data Structures & Algorithms (DSA) track

Warm-up questions

How does a trie count the stored words that start with a prefix in O(L) time?

When should trie nodes keep an array of children instead of a hash map?

Why does a dot wildcard make a trie search slower than an exact search?

Questions with model answers

A contacts app suggests names after every key typed. It holds 200,000 names of about 12 characters each. Would you keep them in a trie? Estimate its nodes and its memory in CPython, and compare it with a sorted list searched by binary search.

Your trie keeps a counter on every node of the words that pass through it, so that it can count words by prefix. Design delete(word). What goes wrong if delete only clears the end-of-word flag, and when should nodes be freed?

A crossword helper keeps 500,000 words in a trie. Patterns such as cros.... come back at once, but patterns such as ....word, with the dots first, are slow. Explain why with numbers, and propose two changes that make leading dots cheap.

A word game checks a 12 × 12 board against a dictionary of 50,000 words: every word spelled by a chain of side-by-side cells that uses no cell twice. One search per word is too slow. Design a faster search, estimate its work, and say how found words are handled.

A router holds 900,000 IPv4 routes, each a prefix such as 10.20.0.0/16, and must find the longest matching prefix for every packet's destination. How would a binary trie answer this, how many steps and nodes does it need, and how would you make lookups faster?