Autocomplete System with Trie in DSA Typescript - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to create a Trie node with an empty children map.

DSA Typescript

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

const node = new TrieNode();
node.children.[1]('a', new TrieNode());

Drag options to blanks, or click blank then click option'

Ainsert

Badd

Cpush

Dset

Attempts:

3 left

💡 Hint

Common Mistakes

Using 'add' which is for Set, not Map.

Using 'push' which is for arrays.

Using 'insert' which is not a Map method.

The Map object uses the 'set' method to add a key-value pair. Here, 'a' is the key and a new TrieNode is the value.

2fill in blank

medium

Complete the code to check if a character exists in the current Trie node's children.

DSA Typescript

function hasChild(node: TrieNode, char: string): boolean {
  return node.children.[1](char);
}

Drag options to blanks, or click blank then click option'

Ahas

Bcontains

Cincludes

Dexists

Attempts:

3 left

💡 Hint

Common Mistakes

Using 'contains' which is not a Map method.

Using 'includes' which is for arrays or strings.

Using 'exists' which is not a Map method.

The Map object uses the 'has' method to check if a key exists.

3fill in blank

hard

Fix the error in the insert method to correctly add characters to the Trie.

DSA Typescript

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

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

Drag options to blanks, or click blank then click option'

Ahas

Bget

Cset

Dadd

Attempts:

3 left

💡 Hint

Common Mistakes

Using 'get' which returns a value, not a boolean.

Using 'set' which adds or updates but does not check existence.

Using 'add' which is not a Map method.

We must check if the character exists using 'has' before adding it with 'set'.

4fill in blank

hard

Fill both blanks to complete the search method that returns true if the word exists in the Trie.

DSA Typescript

search(word: string): boolean {
  let current = this.root;
  for (const char of word) {
    if (!current.children.[1](char)) {
      return false;
    }
    current = current.children.[2](char)!;
  }
  return current.isEndOfWord;
}

Drag options to blanks, or click blank then click option'

Ahas

Bget

Cset

Dadd

Attempts:

3 left

💡 Hint

Common Mistakes

Using 'set' instead of 'get' to retrieve the child node.

Using 'add' which is not a Map method.

Using 'get' to check existence which returns undefined if missing.

Use 'has' to check if the character exists and 'get' to move to the child node.

5fill in blank

hard

Fill all three blanks to complete the autocomplete method that collects all words starting with a prefix.

DSA Typescript

autocomplete(prefix: string): string[] {
  let current = this.root;
  for (const char of prefix) {
    if (!current.children.[1](char)) {
      return [];
    }
    current = current.children.[2](char)!;
  }
  const results: string[] = [];
  function dfs(node: TrieNode, path: string) {
    if (node.isEndOfWord) {
      results.push(path);
    }
    for (const [nextChar, nextNode] of node.children) {
      dfs(nextNode, path + [3]);
    }
  }
  dfs(current, prefix);
  return results;
}

Drag options to blanks, or click blank then click option'

Ahas

Bget

CnextChar

Dchar

Attempts:

3 left

💡 Hint

Common Mistakes

Using 'char' instead of 'nextChar' inside dfs loop.

Using 'set' or 'add' instead of 'has' or 'get'.

Not adding the character to the path string.

Use 'has' to check child existence, 'get' to get the child node, and 'nextChar' to add the next character to the path.