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.