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

Practice - 5 Tasks

1fill in blank

easy

Complete the code to insert a word into the Trie.

DSA Rust

fn insert(&mut self, word: &str) {
    let mut node = &mut self.root;
    for ch in word.chars() {
        node = node.children.entry(ch).or_insert_with(|| TrieNode::new());
    }
    node.is_word = [1];
}

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

Afalse

Btrue

CNone

D0

Attempts:

3 left

💡 Hint

Common Mistakes

Setting is_word to false instead of true.

Forgetting to mark the end of the word.

Marking the end of a word in the Trie requires setting is_word to true.

2fill in blank

medium

Complete the code to check if a node has a child for a given character.

DSA Rust

fn contains_child(&self, ch: char) -> bool {
    self.children.[1](&ch)
}

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

Aget

Bremove

Cinsert

Dcontains_key

Attempts:

3 left

💡 Hint

Common Mistakes

Using get which returns an Option instead of a boolean.

Using insert or remove which modify the map.

The contains_key method checks if a key exists in a HashMap.

3fill in blank

hard

Fix the error in the DFS function to find the longest word.

DSA Rust

fn dfs(node: &TrieNode, path: &mut String, longest: &mut String) {
    if !node.is_word && !path.is_empty() {
        return;
    }
    if path.len() > longest.len() || (path.len() == longest.len() && path < longest) {
        *longest = path.clone();
    }
    for ch in ('a'..='z') {
        if let Some(child) = node.children.get(&ch) {
            path.push(ch);
            dfs(child, path, longest);
            path.[1]();
        }
    }
}

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

Apop

Bremove

Cclear

Dpush

Attempts:

3 left

💡 Hint

Common Mistakes

Using clear which empties the whole string.

Using push which adds characters instead of removing.

After exploring a path, pop removes the last character to backtrack.

4fill in blank

hard

Fill both blanks to build the longest word from the dictionary using Trie.

DSA Rust

fn longest_word(words: Vec<&str>) -> String {
    let mut trie = Trie::new();
    for word in words {
        trie.insert(word);
    }
    let mut longest = String::new();
    let mut path = String::new();
    trie.dfs(&trie.root, &mut path, &mut [1]);
    [2]
}

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

Alongest

Bpath

CString::new()

Dtrie.root

Attempts:

3 left

💡 Hint

Common Mistakes

Returning path which is empty after DFS.

Returning a new empty string instead of longest.

We pass longest to dfs and return longest after traversal.

5fill in blank

hard

Fill all three blanks to complete the TrieNode struct and its new method.

DSA Rust

use std::collections::HashMap;

struct TrieNode {
    children: HashMap<char, [1]>,
    is_word: [2],
}

impl TrieNode {
    fn new() -> Self {
        TrieNode {
            children: HashMap::new(),
            is_word: [3],
        }
    }
}

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

ATrieNode

Bbool

Cfalse

DString

Attempts:

3 left

💡 Hint

Common Mistakes

Using String instead of TrieNode in children map.

Setting is_word to true in new method.

children map chars to TrieNode, is_word is bool, new sets is_word to false.

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 quickly

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 their prefixes, allowing quick prefix checks.

2. Step 2: Relate to longest word search

   Finding the longest word with all prefixes present is easier with Trie traversal.

3. Final Answer:

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

4. Quick Check:

   Trie = prefix-based search [OK]

Hint: Trie is all about prefixes and fast prefix lookups [OK]

Common Mistakes:

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

2. Which of the following Rust code snippets correctly defines a Trie node struct for storing children nodes?

easy

A. struct TrieNode { children: [Option; 26] }

B. struct TrieNode { children: HashMap }

C. struct TrieNode { children: Vec> }

D. struct TrieNode { children: Vec<TrieNode> }

Solution

1. Step 1: Understand Trie children representation

   Each node has fixed 26 children for letters a-z, stored as array of Options.

2. Step 2: Check Rust syntax correctness

   Option allows nullable child nodes; array size 26 matches alphabet.

3. Final Answer:

   struct TrieNode { children: [Option; 26] } -> Option A

4. Quick Check:

   Fixed-size array with Option<Box> = correct Trie node [OK]

Hint: Use fixed-size array with Option<Box> for children in Rust Trie [OK]

Common Mistakes:

• Using Vec without fixed size wastes memory
• Using HashMap without Box causes ownership errors
• Not wrapping children in Option causes panic

3. Given the following Rust code snippet that inserts words into a Trie and finds the longest word with all prefixes present, what will be the printed output?

let words = vec!["a", "app", "ap", "apply", "apple"];
let longest = find_longest_word(words);
println!("{}", longest);

Assume find_longest_word uses a Trie to find the longest word where every prefix is also a word.

medium

A. "apple"

B. "apply"

C. "app"

D. "ap"

Solution

1. Step 1: Check prefixes for each word

   "apple" prefixes: a, ap, app, appl; "appl" missing, so invalid.
   "apply" prefixes: a, ap, app, appl; "appl" missing, invalid.
   "app" prefixes: a, ap, app; all present.
   "ap" prefixes: a, ap; all present.

2. Step 2: Find longest valid word

   "app" is longest word with all prefixes present.

3. Final Answer:

   "app" -> Option C

4. Quick Check:

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

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

Common Mistakes:

• Assuming 'apple' or 'apply' are valid without all prefixes
• Ignoring prefix 'appl' missing
• Choosing shortest word instead of longest

4. The following Rust function attempts to insert words into a Trie and find the longest word with all prefixes present. It compiles but returns an empty string. What is the likely bug?

fn find_longest_word(words: Vec<&str>) -> String {
    let mut trie = Trie::new();
    for word in &words {
        trie.insert(word);
    }
    trie.search_longest_word()
}

// Trie methods:
// insert(&self, word: &str)
// search_longest_word(&self) -> String

medium

A. The function should return &str, not String

B. The insert method should take &mut self, not &self

C. Words vector should be mutable

D. The search_longest_word method should take &mut self, not &self

Solution

1. Step 1: Analyze method signatures

   Inserting words modifies Trie, so insert must take mutable reference &mut self.

2. Step 2: Identify compilation vs runtime issue

   Code compiles but insert called with &self means no actual insertion happens, so Trie remains empty.

3. Final Answer:

   The insert method should take &mut self, not &self -> Option B

4. Quick Check:

   Mutable insert needed for Trie modification [OK]

Hint: Insert modifies Trie; needs &mut self in Rust [OK]

Common Mistakes:

• Thinking search needs mutable reference
• Making words vector mutable unnecessarily
• Returning wrong type String vs &str

5. You have a list of words: ["a", "banana", "app", "appl", "ap", "apply", "apple"]. Using a Trie, which word will be returned as the longest word where every prefix is also a word? Explain why the word "banana" is not chosen.

hard

A. "apple" because "banana" prefixes are missing

B. "apply" because it is longer than "apple"

C. "appl" because "appl" is a prefix of "apple" and "apply"

D. "apple" because all its prefixes exist

Solution

1. Step 1: Check prefixes of each candidate word

   "apple" prefixes: a, ap, app, appl, apple - all present.
   "apply" prefixes: a, ap, app, appl, apply - all present.
   "banana" prefixes: b, ba, ban, bana, banan, banana - none except 'b' likely missing.

2. Step 2: Understand why "banana" is excluded

   Since prefixes like 'b', 'ba' are not in the word list, "banana" is invalid.
   Between "apple" and "apply", both valid, but "apple" is chosen (depends on lex order or implementation).

3. Final Answer:

   "apple" because "banana" prefixes are missing -> Option A

4. Quick Check:

   Missing prefixes exclude "banana" [OK]

Hint: Check all prefixes exist; missing prefixes exclude word [OK]

Common Mistakes:

• Assuming "banana" is valid without prefixes
• Confusing "apply" as longer than "apple"
• Ignoring prefix checks for all words