Longest Word in Dictionary Using Trie in DSA Typescript - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to insert a word into the Trie.

DSA Typescript

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[1];
  }
  node.isEnd = true;
}

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

A.children.has(char)

B.children.set(char)

C.children.get(char)

D.isEnd

Attempts:

3 left

💡 Hint

Common Mistakes

Using .children.set(char) instead of .children.get(char) to move to the child node.

Trying to access node.isEnd instead of child nodes.

We move to the child node corresponding to the current character using node.children.get(char).

2fill in blank

medium

Complete the code to check if a word exists in the Trie.

DSA Typescript

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

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

A.isEnd

B.children

C.has

D.get

Attempts:

3 left

💡 Hint

Common Mistakes

Returning node.children instead of node.isEnd.

Using node.has or node.get which are Map methods, not properties of TrieNode.

To confirm the word exists, we check if the last node marks the end of a word using node.isEnd.

3fill in blank

hard

Fix the error in the DFS function to find the longest word built one character at a time.

DSA Typescript

dfs(node: TrieNode, path: string): string {
  let longest = path;
  for (const [char, child] of node.children) {
    if (child[1]) {
      const word = this.dfs(child, path + char);
      if (word.length > longest.length || (word.length === longest.length && word < longest)) {
        longest = word;
      }
    }
  }
  return longest;
}

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

A.children

B.isEnd

C.has

D.get

Attempts:

3 left

💡 Hint

Common Mistakes

Using child.children or child.has which are incorrect here.

Not checking if child.isEnd, causing invalid words to be included.

We only continue DFS if the child node marks the end of a valid word using child.isEnd.

4fill in blank

hard

Fill both blanks to create a dictionary comprehension that filters words with length greater than 3 and maps them to their lengths.

DSA Typescript

const filteredLengths = {word[1] word of words if word.length [2] 3};

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

A: word.length

B>

C<

D=>

Attempts:

3 left

💡 Hint

Common Mistakes

Using '<' instead of '>' for filtering.

Using '=>' which is for arrow functions, not object literals.

We map each word to its length using ': word.length' and filter words with length greater than 3 using '> 3'.

5fill in blank

hard

Fill all three blanks to create a dictionary comprehension that maps uppercase words to their lengths if length is greater than 2.

DSA Typescript

const result = { [1]: [2] for const word of words if word.length [3] 2 };

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

Aword.toUpperCase()

Bword.length

C>

Dword

Attempts:

3 left

💡 Hint

Common Mistakes

Using 'word' instead of 'word.toUpperCase()' for keys.

Using '<' instead of '>' for filtering.

We map uppercase words (word.toUpperCase()) to their lengths (word.length) filtering words longer than 2 (word.length > 2).

Practice

1. What is the main purpose of using a Trie data structure when finding the longest word in a dictionary?

easy

A. To efficiently store and search words by their prefixes

B. To sort words alphabetically

C. To count the total number of words

D. To reverse the words quickly

Solution

1. Step 1: Understand Trie usage

   A Trie stores words by breaking them into characters and linking nodes for prefixes.

2. Step 2: Connect Trie to longest word search

   This structure allows quick prefix checks, which helps find the longest word built from other words.

3. Final Answer:

   To efficiently store and search words by their prefixes -> Option A

4. Quick Check:

   Trie = prefix search [OK]

Hint: Trie is best for prefix-based word searches [OK]

Common Mistakes:

• Thinking Trie sorts words alphabetically
• Confusing Trie with simple arrays
• Assuming Trie counts words only

2. Which of the following TypeScript code snippets correctly initializes a Trie node with children and an end-of-word flag?

easy

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

B. class TrieNode { children: string[] = []; isEnd: number = 0; }

C. class TrieNode { children: object = {}; isEnd: string = 'false'; }

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

Solution

1. Step 1: Check children type

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

2. Step 2: Check isEnd flag type

   isEnd should be boolean to mark word end, so boolean = false is correct.

3. Final Answer:

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

4. Quick Check:

   Correct types = class TrieNode { children: Map = new Map(); isEnd: boolean = false; } [OK]

Hint: Use Map and boolean for TrieNode [OK]

Common Mistakes:

• Using array instead of Map for children
• Using wrong types for isEnd flag
• Mixing key and value types in Map

3. Given the following TypeScript code snippet that inserts words into a Trie and finds the longest word, what will be the output?

const words = ["a", "app", "apple", "apply", "ap"];
const trie = new Trie();
words.forEach(word => trie.insert(word));
console.log(trie.findLongestWord());

medium

A. "a"

B. "apply"

C. "apple"

D. "app"

Solution

1. Step 1: Insert words into Trie

   Words "a", "app", "apple", "apply", "ap" are inserted. Trie stores prefixes for all.

2. Step 2: Find longest word with all prefixes present

   "app" has all prefixes present: "a", "ap", "app". "apple" and "apply" require "appl" which is not a word in the list.

3. Final Answer:

   "app" -> Option D

4. Quick Check:

   Longest word with all prefixes = "app" [OK]

Hint: Choose longest word with all prefixes present, lex smallest if tie [OK]

Common Mistakes:

• Choosing "apple" or "apply" without checking if "appl" is a word
• Ignoring that intermediate prefixes like "appl" must be full words
• Picking the overall longest word without prefix validation

4. Consider this buggy TypeScript code snippet for inserting words into a Trie:

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

What is the main issue causing a runtime error?

medium

A. The loop does not iterate over all characters

B. The isEnd flag is set before inserting nodes

C. node.children.get(char) can return undefined, causing node to be undefined

D. The children map is not initialized

Solution

1. Step 1: Analyze node update inside loop

   node.children.get(char) may return undefined if key missing, but code assumes it returns TrieNode.

2. Step 2: Identify cause of runtime error

   If undefined assigned to node, next iteration fails accessing children of undefined.

3. Final Answer:

   node.children.get(char) can return undefined, causing node to be undefined -> Option C

4. Quick Check:

   Undefined node from get() causes error [OK]

Hint: Check if get() can return undefined before assignment [OK]

Common Mistakes:

• Ignoring possibility of undefined from Map.get()
• Assuming loop skips characters
• Confusing isEnd flag placement

5. You have a list of words: ["w", "wo", "wor", "worl", "world", "banana", "ban", "bana", "banan"]. Using a Trie, which word will be the longest word in the dictionary where every prefix is also a word in the list?

hard

A. "banana"

B. "world"

C. "banan"

D. "worl"

Solution

1. Step 1: Check prefixes for "world"

   Prefixes: "w", "wo", "wor", "worl" all exist in list.

2. Step 2: Check prefixes for "banana" and "banan"

   "banana" and "banan" are missing shorter prefixes like "b" and "ba" which are not in the list.

3. Step 3: Compare valid longest words

   "world" is longest with all prefixes present; others longer but invalid.

4. Final Answer:

   "world" -> Option B

5. Quick Check:

   Longest word with all prefixes = "world" [OK]

Hint: Check all prefixes exist; longest valid word wins [OK]

Common Mistakes:

• Choosing "banana" ignoring missing prefix like "b"
• Confusing similar prefixes
• Not verifying all prefixes exist