Challenge - 5 Problems
Trie Search Master
Get all challenges correct to earn this badge!
Test your skills under time pressure!
❓ Predict Output
intermediate2:00remaining
Output of Searching a Word in a Trie
What is the output of the following Rust code that inserts words into a Trie and searches for a specific word?
DSA Rust
use std::collections::HashMap;
struct TrieNode {
children: HashMap<char, TrieNode>,
is_end_of_word: bool,
}
impl TrieNode {
fn new() -> Self {
TrieNode {
children: HashMap::new(),
is_end_of_word: 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_of_word = true;
}
fn search(&self, word: &str) -> bool {
let mut node = &self.root;
for ch in word.chars() {
match node.children.get(&ch) {
Some(next_node) => node = next_node,
None => return false,
}
}
node.is_end_of_word
}
}
fn main() {
let mut trie = Trie::new();
trie.insert("cat");
trie.insert("car");
trie.insert("dog");
println!("{}", trie.search("car"));
}Attempts:
2 left
💡 Hint
Think about whether the word 'car' was inserted before searching.
✗ Incorrect
The code inserts the words "cat", "car", and "dog" into the Trie. Then it searches for "car". Since "car" was inserted, the search returns true.
❓ Predict Output
intermediate2:00remaining
Search Result for a Non-Inserted Word
What will be printed when searching for the word "cap" in the following Trie after inserting "cat" and "car"?
DSA Rust
use std::collections::HashMap;
struct TrieNode {
children: HashMap<char, TrieNode>,
is_end_of_word: bool,
}
impl TrieNode {
fn new() -> Self {
TrieNode {
children: HashMap::new(),
is_end_of_word: 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_of_word = true;
}
fn search(&self, word: &str) -> bool {
let mut node = &self.root;
for ch in word.chars() {
match node.children.get(&ch) {
Some(next_node) => node = next_node,
None => return false,
}
}
node.is_end_of_word
}
}
fn main() {
let mut trie = Trie::new();
trie.insert("cat");
trie.insert("car");
println!("{}", trie.search("cap"));
}Attempts:
2 left
💡 Hint
Check if "cap" was inserted or not.
✗ Incorrect
The word "cap" was not inserted into the Trie. The search will fail at the character 'p' because it does not exist in the children of the node for 'a'. Hence, the search returns false.
🔧 Debug
advanced2:00remaining
Identify the Bug in Trie Search Method
The following Rust code attempts to search a word in a Trie but always returns false. What is the bug?
DSA Rust
use std::collections::HashMap;
struct TrieNode {
children: HashMap<char, TrieNode>,
is_end_of_word: bool,
}
impl TrieNode {
fn new() -> Self {
TrieNode {
children: HashMap::new(),
is_end_of_word: 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_of_word = true;
}
fn search(&self, word: &str) -> bool {
let mut node = &self.root;
for ch in word.chars() {
if node.children.contains_key(&ch) {
node = node.children.get(&ch).unwrap();
} else {
return false;
}
}
false
}
}
fn main() {
let mut trie = Trie::new();
trie.insert("hello");
println!("{}", trie.search("hello"));
}Attempts:
2 left
💡 Hint
Look at the return statement after the loop in search.
✗ Incorrect
The search method returns false at the end regardless of whether the word exists. It should return node.is_end_of_word to confirm the word ends here.
🧠 Conceptual
advanced1:30remaining
Understanding Trie Search Complexity
What is the time complexity of searching a word of length n in a Trie containing m words?
Attempts:
2 left
💡 Hint
Consider how many characters you check during search.
✗ Incorrect
Searching a word in a Trie depends only on the length of the word, not the total number of words stored. Each character leads to a child node lookup, so complexity is O(n).
🚀 Application
expert2:30remaining
Result of Searching Prefix vs Whole Word in Trie
Given a Trie with words "apple", "app", and "application" inserted, what will be the output of searching for "app" and "appl" respectively?
Attempts:
2 left
💡 Hint
Remember that search returns true only if the exact word was inserted, not just a prefix.
✗ Incorrect
The word "app" was inserted, so searching "app" returns true. "appl" is only a prefix, not a complete inserted word, so searching "appl" returns false.