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

Practice - 5 Tasks

1fill in blank

easy

Complete the code to insert a word into the Trie.

DSA Javascript

insert(word) {
  let node = this.root;
  for (let 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'

Achildren.has(char)

Bchildren.set(char)

Cchildren.get(char)

Dchildren.delete(char)

Attempts:

3 left

💡 Hint

Common Mistakes

Using set instead of get to move to the child node.

Checking if child exists but not moving to it.

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

2fill in blank

medium

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

DSA Javascript

search(word) {
  let node = this.root;
  for (let 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.isWord

B.found

C.exists

D.isEnd

Attempts:

3 left

💡 Hint

Common Mistakes

Using a wrong property name like isWord or exists.

Returning true without checking if it's the end of a word.

The isEnd property tells if the node marks the end of a valid word.

3fill in blank

hard

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

DSA Javascript

dfs(node, path) {
  if (!node.isEnd && node !== this.root) return;
  if (path.length > this.longest.length) {
    this.longest = path;
  }
  for (let [char, child] of node.children) {
    this.dfs(child, path + [1]);
  }
}

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

Achild

Bchar

Cnode

Dpath

Attempts:

3 left

💡 Hint

Common Mistakes

Adding the child node object instead of the character.

Adding the whole node or path again.

We add the character char to the current path string during DFS.

4fill in blank

hard

Fill both blanks to complete the reduce function that builds an object filtering words with length greater than 3 and mapping them to their lengths.

DSA Javascript

const result = words.reduce((acc, word) => {
  if (word.length [2] 3) {
    acc[word][1] word.length;
  }
  return acc;
}, {});

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

A:

B>

C<

D=

Attempts:

3 left

💡 Hint

Common Mistakes

Using colon instead of equals for object property assignment.

Using less than sign for filtering.

The equals sign = assigns the length as the value for the word key in the accumulator object, and > filters words longer than 3.

5fill in blank

hard

Fill all three blanks to complete the function that finds the longest word in the dictionary using Trie and DFS.

DSA Javascript

function longestWord(words) {
  const trie = new Trie();
  for (const word of words) {
    trie.[1](word);
  }
  trie.longest = "";
  trie.[2](trie.root, "");
  return trie.[3];
}

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

Ainsert

Bdfs

Clongest

Dsearch

Attempts:

3 left

💡 Hint

Common Mistakes

Calling search instead of insert to add words.

Returning dfs instead of the longest word.

Insert words into the Trie, run DFS to find the longest word, then return the longest word.

Practice

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

easy

A. To reverse the words in the dictionary

B. To sort words alphabetically

C. To count the total number of words

D. To efficiently store and search words by their prefixes

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 D

4. Quick Check:

   Trie = prefix search [OK]

Hint: Trie is all about prefixes and fast word lookup [OK]

Common Mistakes:

• Confusing Trie with sorting algorithms
• Thinking Trie reverses words
• Assuming Trie counts words only

2. Which of the following is the correct way to insert a word into a Trie node in JavaScript?

easy

A. node[word[i]] = new TrieNode() if not exists

B. node[word[i]] = word[i]

C. node.push(word[i])

D. node[word] = true

Solution

1. Step 1: Understand Trie node insertion

   Each character of the word is a key in the node object; if missing, create a new TrieNode.

2. Step 2: Identify correct syntax

   Using node[word[i]] = new TrieNode() creates a child node for that character if it doesn't exist.

3. Final Answer:

   node[word[i]] = new TrieNode() if not exists -> Option A

4. Quick Check:

   Insert char as child node [OK]

Hint: Insert chars as keys with new nodes if missing [OK]

Common Mistakes:

• Assigning character directly instead of node
• Using array push on object
• Setting whole word as key instead of chars

3. Given the words ["a", "app", "apple", "apply", "ap"], what is the longest word that can be built one character at a time using the Trie method?

medium

A. "apple"

B. "apply"

C. "app"

D. "ap"

Solution

1. Step 1: Check each word buildability

   Words must be built one char at a time with all prefixes present. "a", "ap", "app" are present, but "apple" and "apply" require "appl" which is missing.

2. Step 2: Identify longest valid word

   "app" is the longest word where all prefixes ("a", "ap", "app") exist in the list.

3. Final Answer:

   "app" -> Option C

4. Quick Check:

   Longest buildable word = "app" [OK]

Hint: Check all prefixes exist for each candidate word [OK]

Common Mistakes:

• Assuming "apple" or "apply" are valid without "appl" prefix
• Ignoring prefix existence
• Choosing shortest word instead of longest

4. What is the bug in this Trie insertion snippet for finding the longest word?

for (let char of word) {
  if (!node[char]) {
    node[char] = {};
  }
  node = node[char];
}
node.isWord = true;

medium

A. No bug, code is correct

B. Missing initialization of root node

C. Not marking the end of word properly

D. Using plain object instead of TrieNode class

Solution

1. Step 1: Analyze insertion logic

   The loop creates child nodes if missing and moves down the Trie correctly.

2. Step 2: Check end of word marking

   Setting node.isWord = true marks the end of the word properly.

3. Final Answer:

   No bug, code is correct -> Option A

4. Quick Check:

   Insertion and marking done correctly [OK]

Hint: Mark end of word after insertion loop [OK]

Common Mistakes:

• Forgetting to mark end of word
• Overcomplicating node creation
• Assuming class needed when object works

5. You have a list of words: ["w", "wo", "wor", "worl", "world", "banana", "ban", "bana", "banan"]. Using a Trie, which word is the longest that can be built one character at a time from other words in the list?

hard

A. "banan"

B. "world"

C. "banana"

D. "worl"

Solution

1. Step 1: Verify prefix existence for each candidate

   For "world": prefixes "w", "wo", "wor", "worl", "world" all exist. For "banana": prefixes "b", "ba", "ban", "bana", "banan", "banana" -- but "b" and "ba" are missing. Similarly, "banan" misses "b" and "ba".

2. Step 2: Compare longest buildable words

   "world" is the longest word where all prefixes from length 1 to full length exist in the list.

3. Final Answer:

   "world" -> Option B

4. Quick Check:

   Longest buildable word = "world" [OK]

Hint: Check all prefixes exist before choosing longest word [OK]

Common Mistakes:

• Choosing "banana" without all prefixes
• Ignoring missing prefixes
• Confusing partial prefixes as complete