Autocomplete System with Trie in DSA Typescript - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Trie Insertion and Search

What is the output of the following TypeScript code that inserts words into a Trie and searches for a prefix?

DSA Typescript

class TrieNode {
  children: Map<string, TrieNode> = new Map();
  isEndOfWord: boolean = false;
}

class Trie {
  root: TrieNode = new TrieNode();

  insert(word: string): void {
    let node = this.root;
    for (const char of word) {
      if (!node.children.has(char)) {
        node.children.set(char, new TrieNode());
      }
      node = node.children.get(char)!;
    }
    node.isEndOfWord = true;
  }

  searchPrefix(prefix: string): boolean {
    let node = this.root;
    for (const char of prefix) {
      if (!node.children.has(char)) {
        return false;
      }
      node = node.children.get(char)!;
    }
    return true;
  }
}

const trie = new Trie();
trie.insert("apple");
trie.insert("app");
console.log(trie.searchPrefix("app"));
console.log(trie.searchPrefix("appl"));
console.log(trie.searchPrefix("banana"));

A

true
false
false

B

false
false
true

C

false
true
false

D

true
true
false

💡 Hint

Think about whether the prefix exists in the Trie after insertion.

The prefix "app" exists because both "app" and "apple" were inserted. "appl" is also a prefix of "apple" so it returns true. "banana" was never inserted, so it returns false.

🧠 Conceptual

intermediate

Understanding Trie Node Structure

Which of the following best describes the role of the 'isEndOfWord' boolean in a Trie node?

A It marks the node as the end of a valid word stored in the Trie.

B It counts how many words pass through this node.

C It stores the character value of the node.

D It indicates if the node has any children nodes.

💡 Hint

Think about how the Trie knows when a word finishes.

The 'isEndOfWord' flag tells us if the path from root to this node forms a complete word stored in the Trie.

🔧 Debug

advanced

Find the Bug in Autocomplete Suggestion Function

Given the following incomplete autocomplete function in a Trie, which option correctly fixes the bug causing it to return an empty list always?

DSA Typescript

function autocomplete(node: TrieNode, prefix: string): string[] {
  const results: string[] = [];
  function dfs(currentNode: TrieNode, path: string) {
    if (currentNode.isEndOfWord) {
      results.push(path);
    }
    for (const [char, childNode] of currentNode.children) {
      dfs(childNode, path + char);
    }
  }
  dfs(node, prefix);
  return results;
}

// Usage:
// const results = autocomplete(trie.root, "app");
// console.log(results);

A Add a return statement inside the for loop to stop recursion early

B Before calling dfs, traverse the Trie to the node matching prefix, then call dfs on that node with empty string

C Change dfs(node, prefix) to dfs(node, "")

D Change dfs(node, prefix) to dfs(node.children.get(prefix[prefix.length - 1])!, prefix)

💡 Hint

The function must start DFS from the node representing the prefix, not the root.

To get autocomplete suggestions for a prefix, first find the node corresponding to the prefix, then run DFS from there with an empty path to collect suffixes.

🚀 Application

advanced

Predict the Output of Autocomplete Suggestions

After inserting the words ["dog", "deer", "deal"] into a Trie, what will be the output of autocomplete suggestions for prefix "de"?

DSA Typescript

const trie = new Trie();
["dog", "deer", "deal"].forEach(word => trie.insert(word));

function findNode(prefix: string): TrieNode | null {
  let node = trie.root;
  for (const char of prefix) {
    if (!node.children.has(char)) return null;
    node = node.children.get(char)!;
  }
  return node;
}

function autocomplete(node: TrieNode, prefix: string): string[] {
  const results: string[] = [];
  function dfs(currentNode: TrieNode, path: string) {
    if (currentNode.isEndOfWord) results.push(prefix + path);
    for (const [char, childNode] of currentNode.children) {
      dfs(childNode, path + char);
    }
  }
  dfs(node, "");
  return results;
}

const node = findNode("de");
const suggestions = node ? autocomplete(node, "de") : [];
console.log(suggestions);

A ["dog", "deer", "deal"]

B ["de"]

C ["deer", "deal"]

D []

💡 Hint

Only words starting with "de" should be suggested.

The words "deer" and "deal" start with "de" and are in the Trie. "dog" does not start with "de" so it is excluded.

🧠 Conceptual

expert

Time Complexity of Autocomplete with Trie

What is the time complexity to find all autocomplete suggestions for a prefix of length p in a Trie containing n words, assuming k suggestions are returned?

A O(p + k * m), where m is average length of suggestions

B O(n * p), because all words must be checked for prefix

C O(k), since only suggestions are returned

D O(p * n), because prefix search multiplies by total words

💡 Hint

Consider the cost to reach the prefix node and then collect suggestions.

Finding the prefix node takes O(p) time. Collecting k suggestions requires traversing their nodes, roughly O(k * m) where m is average suggestion length.

Practice

1. What is the main purpose of using a Trie in an autocomplete system?

easy

A. To efficiently store and search prefixes of words

B. To sort words alphabetically

C. To count the frequency of words

D. To encrypt the stored words

Solution

1. Step 1: Understand the role of Trie in prefix search

   A Trie is a tree-like data structure designed to store strings by their prefixes, allowing fast prefix-based searches.

2. Step 2: Connect Trie usage to autocomplete

   Autocomplete requires quick lookup of words starting with a given prefix, which Trie supports efficiently.

3. Final Answer:

   To efficiently store and search prefixes of words -> Option A

4. Quick Check:

   Trie = prefix search [OK]

Hint: Trie is built for prefix-based fast search [OK]

Common Mistakes:

• Confusing Trie with sorting algorithms
• Thinking Trie encrypts data
• Assuming Trie counts word frequency only

2. Which of the following is the correct TypeScript syntax to define a Trie node with children as a Map of characters to Trie nodes?

easy

A. class TrieNode { children: Array<string> = []; isEnd: boolean = false; }

B. class TrieNode { children: Map = new Map(); isEnd: boolean = false; }

C. class TrieNode { children: string[] = []; isEnd: boolean = true; }

D. class TrieNode { children: Map = new Map(); isEnd: boolean = false; }

Solution

1. Step 1: Identify correct data type for children

   Children should map characters (string) to TrieNode objects, so Map is correct.

2. Step 2: Check initialization and isEnd flag

   Children initialized as new Map(), and isEnd defaults to false indicating not end of word initially.

3. Final Answer:

   class TrieNode { children: Map = new Map(); isEnd: boolean = false; } -> Option B

4. Quick Check:

   Map for children [OK]

Hint: Children map chars to nodes using Map [OK]

Common Mistakes:

• Using array instead of Map for children
• Using number keys instead of string keys
• Setting isEnd to true by default

3. Given the following TypeScript code snippet for inserting words into a Trie and searching for prefix suggestions, what will be the output of autocomplete.getSuggestions('ca')?

class TrieNode {
  children: Map = new Map();
  isEnd: boolean = false;
}

class AutocompleteSystem {
  root: TrieNode = new TrieNode();

  insert(word: string) {
    let node = this.root;
    for (const char of word) {
      if (!node.children.has(char)) {
        node.children.set(char, new TrieNode());
      }
      node = node.children.get(char)!;
    }
    node.isEnd = true;
  }

  getSuggestions(prefix: string): string[] {
    let node = this.root;
    for (const char of prefix) {
      if (!node.children.has(char)) return [];
      node = node.children.get(char)!;
    }
    const results: string[] = [];
    const dfs = (currNode: TrieNode, path: string) => {
      if (currNode.isEnd) results.push(path);
      for (const [ch, nextNode] of currNode.children) {
        dfs(nextNode, path + ch);
      }
    };
    dfs(node, prefix);
    return results;
  }
}

const autocomplete = new AutocompleteSystem();
autocomplete.insert('cat');
autocomplete.insert('car');
autocomplete.insert('cap');
autocomplete.insert('dog');
console.log(autocomplete.getSuggestions('ca'));

medium

A. ["cat", "car"]

B. ["dog"]

C. []

D. ["cat", "car", "cap"]

Solution

1. Step 1: Insert words and traverse prefix 'ca'

   Words 'cat', 'car', 'cap' are inserted. Searching prefix 'ca' finds node with children 't', 'r', 'p'.

2. Step 2: DFS collects all words starting with 'ca'

   DFS from 'ca' node collects 'cat', 'car', and 'cap' as all end nodes under that prefix.

3. Final Answer:

   ["cat", "car", "cap"] -> Option D

4. Quick Check:

   Prefix 'ca' matches cat, car, cap [OK]

Hint: DFS from prefix node collects all words [OK]

Common Mistakes:

• Returning empty list if prefix found
• Returning unrelated words like 'dog'
• Missing one or more words starting with prefix

4. The following TypeScript code for the insert method in a Trie has a bug. What is the bug?

insert(word: string) {
  let node = this.root;
  for (const char of word) {
    if (!node.children.has(char)) {
      node.children.set(char, new TrieNode());
    }
    node = node.children.get(char);
  }
  node.isEnd = true;
}

medium

A. Missing non-null assertion operator (!) when getting child node

B. Children map should be an array, not Map

C. isEnd should be set to false, not true

D. Loop should iterate over indices, not characters

Solution

1. Step 1: Identify potential null or undefined access

   node.children.get(char) can return undefined if key missing, so TypeScript requires non-null assertion or check.

2. Step 2: Fix by adding non-null assertion operator

   Adding '!' after get(char) tells TypeScript the value is not undefined, fixing the bug.

3. Final Answer:

   Missing non-null assertion operator (!) when getting child node -> Option A

4. Quick Check:

   Use get(char)! to avoid undefined [OK]

Hint: Use '!' after get() to assure non-null [OK]

Common Mistakes:

• Ignoring TypeScript undefined error
• Changing data structure unnecessarily
• Setting isEnd incorrectly

5. You want to extend the autocomplete system to return suggestions sorted by their frequency of insertion (most frequent first). Which data structure modification is best to support this efficiently?

hard

A. Store all words in a separate array and sort on each query

B. Use a binary search tree instead of a Trie

C. Add a frequency count field to each Trie node marking end of word

D. Remove the isEnd flag and rely on children count

Solution

1. Step 1: Understand frequency tracking in Trie

   Adding a frequency count to nodes marking word ends allows tracking how often each word was inserted.

2. Step 2: Use frequency to sort suggestions efficiently

   During DFS for suggestions, use frequency counts to sort or prioritize words without extra data structures.

3. Final Answer:

   Add a frequency count field to each Trie node marking end of word -> Option C

4. Quick Check:

   Frequency field in Trie nodes enables sorting [OK]

Hint: Track frequency in nodes to sort suggestions fast [OK]

Common Mistakes:

• Sorting all words on each query (slow)
• Replacing Trie with BST loses prefix efficiency
• Removing isEnd loses word boundary info