Practice - 5 Tasks
Answer the questions below
1fill in blank
easyComplete the code to create a new Trie node with empty children.
DSA Rust
struct TrieNode {
children: [Option<Box<TrieNode>>; 26],
is_end_of_word: bool,
}
impl TrieNode {
fn new() -> Self {
TrieNode {
children: [1],
is_end_of_word: false,
}
}
} Drag options to blanks, or click blank then click option'
Attempts:
3 left
💡 Hint
Common Mistakes
Using Some without a value causes errors.
Trying to initialize with zeros instead of None.
Using Box::new without creating actual nodes.
✗ Incorrect
The children array should be initialized with None for each of the 26 letters, so [None; 26] is correct.
2fill in blank
mediumComplete the code to insert a character into the Trie children array.
DSA Rust
fn insert_char(&mut self, ch: char) {
let index = (ch as usize) - ('a' as usize);
if self.children[index].is_none() {
self.children[index] = Some(Box::new([1]));
}
} Drag options to blanks, or click blank then click option'
Attempts:
3 left
💡 Hint
Common Mistakes
Assigning None instead of a new node.
Using the type name without calling new().
Trying to box the type instead of the instance.
✗ Incorrect
We need to create a new TrieNode instance using TrieNode::new() to insert at the child position.
3fill in blank
hardFix the error in the search function to correctly check if a prefix exists in the Trie.
DSA Rust
fn search_prefix(&self, prefix: &str) -> bool {
let mut node = self;
for ch in prefix.chars() {
let index = (ch as usize) - ('a' as usize);
match &node.children[index] {
Some(next_node) => node = [1],
None => return false,
}
}
true
} Drag options to blanks, or click blank then click option'
Attempts:
3 left
💡 Hint
Common Mistakes
Dereferencing the Box causing type mismatch.
Using &next_node which is a reference to a reference.
Trying to access children again instead of moving forward.
✗ Incorrect
We assign node to the reference inside Some, which is next_node, to continue traversal.
4fill in blank
hardFill both blanks to complete the insert function that marks the end of a word in the Trie.
DSA Rust
fn insert(&mut self, word: &str) {
let mut node = self;
for ch in word.chars() {
let index = (ch as usize) - ('a' as usize);
if node.children[index].is_none() {
node.children[index] = Some(Box::new([1]));
}
node = node.children[index].as_mut().unwrap();
}
node.[2] = true;
} Drag options to blanks, or click blank then click option'
Attempts:
3 left
💡 Hint
Common Mistakes
Using wrong field names for the end marker.
Not creating new nodes properly.
Forgetting to unwrap the Option before assignment.
✗ Incorrect
We create new nodes with TrieNode::new() and mark the end of word by setting is_end_of_word to true.
5fill in blank
hardFill all three blanks to complete a function that returns all words in the Trie starting with a given prefix.
DSA Rust
fn collect_words(node: &TrieNode, prefix: String, results: &mut Vec<String>) {
if node.[1] {
results.push(prefix.clone());
}
for i in 0..26 {
if let Some(child) = &node.children[i] {
let ch = (i as u8 + b'a') as char;
collect_words(child, prefix.clone() + &[2], results);
}
}
}
fn words_with_prefix(root: &TrieNode, prefix: &str) -> Vec<String> {
let mut node = root;
for ch in prefix.chars() {
let index = (ch as usize) - ('a' as usize);
match &node.children[index] {
Some(next_node) => node = next_node,
None => return vec![],
}
}
let mut results = Vec::new();
collect_words(node, prefix.to_string(), &mut [3]);
results
} Drag options to blanks, or click blank then click option'
Attempts:
3 left
💡 Hint
Common Mistakes
Using wrong field names for word end check.
Concatenating char without converting to string.
Passing wrong variable for results vector.
✗ Incorrect
We check is_end_of_word to add words, append ch as string to prefix, and pass results vector to collect_words.