Challenge - 5 Problems
Trie Prefix Search Master
Get all challenges correct to earn this badge!
Test your skills under time pressure!
❓ Predict Output
intermediate2:00remaining
Output of Prefix Search Result in Trie
What is the output of the following Rust code that inserts words into a Trie and searches for words with prefix "app"?
DSA Rust
struct TrieNode {
children: std::collections::HashMap<char, TrieNode>,
is_end: bool,
}
impl TrieNode {
fn new() -> Self {
TrieNode {
children: std::collections::HashMap::new(),
is_end: false,
}
}
}
struct Trie {
root: TrieNode,
}
impl Trie {
fn new() -> Self {
Trie {
root: TrieNode::new(),
}
}
fn insert(&mut self, word: &str) {
let mut node = &mut self.root;
for ch in word.chars() {
node = node.children.entry(ch).or_insert(TrieNode::new());
}
node.is_end = true;
}
fn search_prefix(&self, prefix: &str) -> Vec<String> {
fn dfs(node: &TrieNode, prefix: &str, results: &mut Vec<String>) {
if node.is_end {
results.push(prefix.to_string());
}
for (ch, child) in &node.children {
let mut new_prefix = prefix.to_string();
new_prefix.push(*ch);
dfs(child, &new_prefix, results);
}
}
let mut node = &self.root;
for ch in prefix.chars() {
if let Some(next_node) = node.children.get(&ch) {
node = next_node;
} else {
return vec![];
}
}
let mut results = Vec::new();
dfs(node, prefix, &mut results);
results
}
}
fn main() {
let mut trie = Trie::new();
trie.insert("apple");
trie.insert("app");
trie.insert("application");
trie.insert("bat");
let result = trie.search_prefix("app");
println!("{:?}", result);
}Attempts:
2 left
💡 Hint
Think about all words starting with the prefix "app" inserted in the Trie.
✗ Incorrect
The search_prefix method finds the node matching the prefix "app" and collects all words starting from there. Since "app", "apple", and "application" were inserted, all three are returned.
🧠 Conceptual
intermediate1:30remaining
Number of Nodes in Trie after Insertions
After inserting the words ["cat", "car", "cart", "dog"] into an empty Trie, how many nodes does the Trie contain?
Attempts:
2 left
💡 Hint
Count shared prefixes carefully to avoid double counting nodes.
✗ Incorrect
The words share prefixes: "cat" and "car" share 'c' and 'a', "cart" extends "car" by one letter. "dog" is separate. Counting nodes: c(1), a(2), t(3), r(4), t(5), d(6), o(7), g(8), plus root(9).
🔧 Debug
advanced2:00remaining
Identify the Bug in Trie Insert Method
What error will occur when running this Rust Trie insert method code snippet?
DSA Rust
fn insert(&mut self, word: &str) { let mut node = &self.root; for ch in word.chars() { node = node.children.entry(ch).or_insert(TrieNode::new()); } node.is_end = true; }
Attempts:
2 left
💡 Hint
Check if `node` is mutable or immutable reference when assigning.
✗ Incorrect
The code uses `let mut node = &self.root;` which is an immutable reference. Trying to mutate children via `entry` requires mutable reference, causing a compile error.
🚀 Application
advanced1:30remaining
Find All Words with Prefix in Trie
Given a Trie with words inserted: ["tree", "trie", "algo", "assoc", "all", "also"], which of the following lists is returned by searching prefix "al"?
Attempts:
2 left
💡 Hint
Look for all words starting with "al".
✗ Incorrect
Words starting with "al" are "algo", "all", and "also". "assoc" starts with "as" so it is excluded.
❓ Predict Output
expert1:30remaining
Output of Trie Prefix Search with No Matches
What is the output of the following Rust code snippet when searching prefix "xyz" in the Trie?
DSA Rust
let mut trie = Trie::new(); trie.insert("hello"); trie.insert("world"); trie.insert("help"); let result = trie.search_prefix("xyz"); println!("{:?}", result);
Attempts:
2 left
💡 Hint
If prefix does not exist, search returns empty list.
✗ Incorrect
Since no word starts with "xyz", the search_prefix returns an empty vector, printed as [].