Challenge - 5 Problems
Trie Mastery Badge
Get all challenges correct to earn this badge!
Test your skills under time pressure!
❓ Predict Output
intermediate2:00remaining
Output of Longest Word Found Using Trie
What is the output of the following Rust code that builds a Trie from a list of words and finds the longest word where all prefixes are present?
DSA Rust
struct TrieNode {
children: [Option<Box<TrieNode>>; 26],
is_end: bool,
}
impl TrieNode {
fn new() -> Self {
Self {
children: Default::default(),
is_end: false,
}
}
}
struct Trie {
root: TrieNode,
}
impl Trie {
fn new() -> Self {
Self { root: TrieNode::new() }
}
fn insert(&mut self, word: &str) {
let mut node = &mut self.root;
for &b in word.as_bytes() {
let idx = (b - b'a') as usize;
if node.children[idx].is_none() {
node.children[idx] = Some(Box::new(TrieNode::new()));
}
node = node.children[idx].as_mut().unwrap();
}
node.is_end = true;
}
fn longest_word(&self) -> String {
let mut result = String::new();
let mut path = Vec::new();
self.dfs(&self.root, &mut path, &mut result);
result
}
fn dfs(&self, node: &TrieNode, path: &mut Vec<u8>, result: &mut String) {
if node != &self.root && !node.is_end {
return;
}
if path.len() > result.len() {
*result = String::from_utf8(path.clone()).unwrap();
}
for i in 0..26 {
if let Some(child) = &node.children[i] {
path.push(b'a' + i as u8);
self.dfs(child, path, result);
path.pop();
}
}
}
}
fn main() {
let words = vec!["w","wo","wor","worl","world"];
let mut trie = Trie::new();
for w in &words {
trie.insert(w);
}
println!("{}", trie.longest_word());
}Attempts:
2 left
💡 Hint
Think about the longest word where all prefixes are also words in the list.
✗ Incorrect
The code inserts all words into a Trie and then uses DFS to find the longest word such that every prefix of the word is also marked as an end of a word. The word "world" has all prefixes ("w", "wo", "wor", "worl") present, so it is the longest valid word.
🧠 Conceptual
intermediate1:30remaining
Understanding Trie Node Structure
In a Trie node implementation for lowercase English letters, why is an array of size 26 used for children nodes instead of other data structures?
Attempts:
2 left
💡 Hint
Think about how fast you can find a child node for a given character.
✗ Incorrect
Using an array of size 26 allows direct indexing for each lowercase English letter, giving O(1) time to access child nodes. Other structures like linked lists or hash maps may have slower access times.
🔧 Debug
advanced2:30remaining
Identify the Bug in Trie Longest Word Search
Given the following snippet from a Trie DFS function, what is the bug that causes incorrect longest word detection?
fn dfs(&self, node: &TrieNode, path: &mut Vec, result: &mut String) {
if node != &self.root && !node.is_end {
return;
}
if path.len() >= result.len() {
*result = String::from_utf8(path.clone()).unwrap();
}
for i in 0..26 {
if let Some(child) = &node.children[i] {
path.push(b'a' + i as u8);
self.dfs(child, path, result);
path.pop();
}
}
}
Attempts:
2 left
💡 Hint
Consider what happens when two words have the same length.
✗ Incorrect
Using '>=' allows words of the same length to overwrite the current result, which may cause lexicographically smaller words to replace longer or preferred words. Changing to '>' ensures only strictly longer words update the result.
🚀 Application
advanced2:00remaining
Longest Word with All Prefixes Present
Given a list of words, which approach best finds the longest word such that every prefix of the word is also in the list?
Attempts:
2 left
💡 Hint
Think about a data structure that efficiently stores prefixes.
✗ Incorrect
A Trie efficiently stores prefixes and allows DFS to find the longest word with all prefixes present. Other methods are less efficient or do not directly support prefix checks.
📝 Syntax
expert2:30remaining
Correct Rust Syntax for Trie Children Initialization
Which option correctly initializes the children array in a Rust TrieNode struct for 26 lowercase letters?
DSA Rust
struct TrieNode {
children: [Option<Box<TrieNode>>; 26],
is_end: bool,
}
impl TrieNode {
fn new() -> Self {
Self {
children: /* fill here */,
is_end: false,
}
}
}Attempts:
2 left
💡 Hint
Think about fixed-size arrays and default values in Rust.
✗ Incorrect
In Rust, fixed-size arrays can be initialized with a repeated value using [value; size]. Here, [None; 26] correctly initializes the array with 26 None values. vec! creates a vector, not an array. Option::None is not valid syntax. Box::new(None) is invalid because None is not a Box.