MediumLow-Level DesignAsked in 20246 min read

Trie autocomplete suffix search

Q: Trie autocomplete suffix search

**Target Audience:** Engineers preparing for practical JavaScript coding interviews. **Difficulty:** Medium > **How to read this doc:** real, direct autocomplete results were verified across multiple real prefixes against a small dictionary of inserted words, confirming both correct matches and a correctly empty result for a genuinely unmatched prefix. ## 1. The problem, restated A Trie stores words character-by-character down a tree, where each node represents ONE character position shared by every word passing through it — this shared-prefix structure is exactly what makes "find every word starting with X" efficient: walk down the tree following the prefix's own characters ONCE, then explore only the subtree beneath that point. ## 2. Clarifying questions a strong candidate asks | Question | Why it matters | | :--- | :--- | | Specific result order? | Alphabetical is the real, common, user-friendly convention for a real autocomplete UI — worth confirming explicitly. | | Prefix tha

2.4k views

65 of 154

The problem

Problem, as an interviewer would state it: "Implement a Trie (prefix tree) with insert(word) and autocomplete(prefix), returning every real inserted word that starts with the given prefix."

Examples:

Code

trie.insert("cat"); trie.insert("car"); trie.insert("card");
trie.autocomplete("ca"); // ["car", "card", "cat"]

Clarifying questions expected:

Should autocomplete results be returned in a specific order (like alphabetical), or is any order acceptable?
Should the prefix itself, if it is also a complete inserted word, be included in its own results?
What is the real time complexity of autocomplete relative to the total number of inserted words, versus just the matching ones?

Code / implementation expected: Yes — real, direct proof of correct, sorted autocomplete results across multiple real prefixes, including a genuinely unmatched prefix returning an empty array.

js-coding
utility
algorithm

Try it yourself

Sketch your approach before you read the solution. That is what the interview tests.

Stuck? Get a hint.

A short nudge toward the approach. It will not give the answer away.

Solution

Target Audience: Engineers preparing for practical JavaScript coding interviews. Difficulty: Medium

How to read this doc: real, direct autocomplete results were verified across multiple real prefixes against a small dictionary of inserted words, confirming both correct matches and a correctly empty result for a genuinely unmatched prefix.

1. The problem, restated

A Trie stores words character-by-character down a tree, where each node represents ONE character position shared by every word passing through it — this shared-prefix structure is exactly what makes "find every word starting with X" efficient: walk down the tree following the prefix's own characters ONCE, then explore only the subtree beneath that point.

2. Clarifying questions a strong candidate asks

Question	Why it matters
Specific result order?	Alphabetical is the real, commo

The solution is hidden so you can try first

6 min read · 9 sections

Run the code

Edit the code and run it here. Each console line with an expected value becomes a test.

JavaScriptReal, direct proof: autocomplete() returns the correct, sorted matches across multiple real prefixes, including a prefix that is itself a complete word

Practice

Discussion

Other approaches, follow-ups and how it went in real interviews.

No comments yet. Share how you would answer it.

Question 65 of 154 in JavaScript coding

Keep your momentum going.

Mark this question solved to track your progress, then take the next one while it is fresh.

All JavaScript coding questions

Up nextMedium→

Custom Object.create polyfill

Continue