Trie vs Hash Map for Prefix Matching in DSA Rust - Compare & Choose

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Prefix Search Using 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, Box<TrieNode>>,
    is_end: bool,
}

impl TrieNode {
    fn new() -> Self {
        TrieNode {
            children: std::collections::HashMap::new(),
            is_end: false,
        }
    }

    fn insert(&mut self, word: &str) {
        let mut node = self;
        for ch in word.chars() {
            node = node.children.entry(ch).or_insert(Box::new(TrieNode::new())).as_mut();
        }
        node.is_end = true;
    }

    fn starts_with(&self, prefix: &str) -> Vec<String> {
        fn dfs(node: &TrieNode, prefix: &str, path: &mut String, results: &mut Vec<String>) {
            if node.is_end {
                results.push(path.clone());
            }
            for (ch, child) in &node.children {
                path.push(*ch);
                dfs(child, prefix, path, results);
                path.pop();
            }
        }

        let mut node = self;
        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();
        let mut path = prefix.to_string();
        dfs(node, prefix, &mut path, &mut results);
        results
    }
}

fn main() {
    let mut trie = TrieNode::new();
    trie.insert("apple");
    trie.insert("app");
    trie.insert("application");
    trie.insert("bat");
    let result = trie.starts_with("app");
    println!("{:?}", result);
}

A ["app", "apple", "application"]

B ["apple", "application"]

C ["app"]

D []

💡 Hint

Think about all words inserted that start with "app" including the prefix itself.

The Trie stores all inserted words. The prefix search returns all words starting with "app" including "app" itself, "apple", and "application".

🧠 Conceptual

intermediate

Why Use Trie Over Hash Map for Prefix Matching?

Which of the following is the main advantage of using a Trie over a Hash Map for prefix matching?

A Trie allows efficient prefix search by traversing nodes character by character.

B Hash Map uses less memory than Trie for storing prefixes.

C Hash Map can directly store all prefixes without extra processing.

D Trie requires less code to implement than Hash Map.

💡 Hint

Think about how prefix search works in both data structures.

Trie stores characters in a tree structure allowing quick traversal for prefixes, while Hash Map requires checking all keys or storing all prefixes explicitly.

❓ Predict Output

advanced

Output of Prefix Search Using Hash Map with All Prefixes

What is the output of this Rust code that stores all prefixes in a Hash Map and queries for prefix "app"?

DSA Rust

use std::collections::HashMap;

fn main() {
    let words = vec!["apple", "app", "application", "bat"];
    let mut prefix_map: HashMap<String, Vec<String>> = HashMap::new();

    for word in &words {
        for i in 1..=word.len() {
            let prefix = &word[..i];
            prefix_map.entry(prefix.to_string()).or_default().push(word.to_string());
        }
    }

    let result = prefix_map.get("app");
    match result {
        Some(list) => println!("{:?}", list),
        None => println!("[]"),
    }
}

A []

B ["app", "application"]

C ["apple", "application"]

D ["apple", "app", "application"]

💡 Hint

All words starting with "app" are stored under that prefix key.

The code stores every prefix of each word as a key in the Hash Map with a list of words that have that prefix. Querying "app" returns all words starting with "app".

🔧 Debug

advanced

Identify the Bug in Trie Prefix Search

What error will this Rust Trie prefix search code produce when searching for prefix "cat" after inserting "car" and "cart"?

DSA Rust

struct TrieNode {
    children: std::collections::HashMap<char, Box<TrieNode>>,
    is_end: bool,
}

impl TrieNode {
    fn new() -> Self {
        TrieNode {
            children: std::collections::HashMap::new(),
            is_end: false,
        }
    }

    fn insert(&mut self, word: &str) {
        let mut node = self;
        for ch in word.chars() {
            node = node.children.entry(ch).or_insert(Box::new(TrieNode::new())).as_mut();
        }
        node.is_end = true;
    }

    fn starts_with(&self, prefix: &str) -> Vec<String> {
        let mut node = self;
        for ch in prefix.chars() {
            node = node.children.get(&ch).unwrap();
        }
        vec![prefix.to_string()]
    }
}

fn main() {
    let mut trie = TrieNode::new();
    trie.insert("car");
    trie.insert("cart");
    let result = trie.starts_with("cat");
    println!("{:?}", result);
}

A ["cat"]

B []

C panic at 'called `Option::unwrap()` on a `None` value'

D Compilation error due to missing return type

💡 Hint

Check what happens when prefix characters are not found in children.

The code uses unwrap() on an Option that is None when the prefix character 't' is not found under 'ca'. This causes a runtime panic.

🧠 Conceptual

expert

Memory Efficiency Comparison: Trie vs Hash Map for Large Prefix Sets

Which statement best describes memory usage when storing a large dictionary of words for prefix matching using Trie vs Hash Map storing all prefixes explicitly?

A Both use the same memory because they store all prefixes explicitly.

B Trie uses less memory because it shares common prefix nodes, while Hash Map stores each prefix separately.

C Trie uses more memory because it stores pointers for each character node.

D Hash Map uses less memory because it stores only prefixes as keys without extra nodes.

💡 Hint

Consider how common prefixes are stored in Trie versus Hash Map.

Trie shares nodes for common prefixes, reducing memory usage, while Hash Map stores each prefix as a separate key, increasing memory usage.

Practice

1. Which data structure is generally more efficient for prefix matching in a large set of strings?

easy

A. Linked List, because it allows easy insertion and deletion

B. Hash Map, because it provides constant time lookup for any key

C. Array, because it stores elements in contiguous memory

D. Trie, because it stores common prefixes once and allows fast prefix queries

Solution

1. Step 1: Understand prefix matching requirements

   Prefix matching needs to find all strings starting with a given prefix efficiently.

2. Step 2: Compare Trie and Hash Map for prefix queries

   Trie stores common prefixes once and allows traversal by characters, making prefix queries fast. Hash Map is good for exact key lookup but not for prefix searches.

3. Final Answer:

   Trie, because it stores common prefixes once and allows fast prefix queries -> Option D

4. Quick Check:

   Prefix matching = Trie [OK]

Hint: Prefix queries need shared paths, so Trie is best [OK]

Common Mistakes:

• Thinking Hash Map supports prefix queries efficiently
• Confusing exact lookup with prefix search
• Assuming arrays or lists are good for prefix matching

2. Which Rust code snippet correctly declares a HashMap to store strings as keys and integers as values?

easy

A. let map = HashMap::new();

B. let map: HashMap = HashMap::new();

C. let map: std::collections::HashMap = std::collections::HashMap::new();

D. let map = HashMap();

Solution

1. Step 1: Check correct HashMap declaration syntax in Rust

   Rust requires specifying types inside angle brackets and calling HashMap::new() without parameters.

2. Step 2: Validate each option

   let map: std::collections::HashMap = std::collections::HashMap::new(); correctly declares a HashMap with String keys and i32 values using full path and new().

3. Final Answer:

   let map: std::collections::HashMap = std::collections::HashMap::new(); -> Option C

4. Quick Check:

   Correct Rust HashMap syntax = let map: std::collections::HashMap = std::collections::HashMap::new(); [OK]

Hint: Use HashMap::new() with type annotations for keys and values [OK]

Common Mistakes:

• Using parentheses instead of ::new()
• Swapping key and value types
• Omitting type annotations when needed

3. Given the following Rust code using a Trie for prefix matching, what will be the output?

struct TrieNode {
    children: std::collections::HashMap,
    is_end: bool,
}

impl TrieNode {
    fn new() -> Self {
        TrieNode { children: std::collections::HashMap::new(), is_end: false }
    }
}

fn main() {
    let mut root = TrieNode::new();
    // Insert "cat"
    let mut node = &mut root;
    for c in "cat".chars() {
        node = node.children.entry(c).or_insert(TrieNode::new());
    }
    node.is_end = true;

    // Check prefix "ca"
    let mut node = &root;
    let mut found = true;
    for c in "ca".chars() {
        if let Some(next) = node.children.get(&c) {
            node = next;
        } else {
            found = false;
            break;
        }
    }
    println!("{}", found);
}

medium

A. false

B. Compilation error

C. true

D. Runtime panic

Solution

1. Step 1: Analyze TrieNode struct definition

   TrieNode { children: HashMap, ... } creates a recursive type without indirection (e.g., Box<TrieNode>). Rust cannot compute the size of TrieNode, resulting in a compilation error.

2. Step 2: Confirm error prevents execution

   Code fails to compile, so no output or runtime behavior occurs.

3. Final Answer:

   Compilation error -> Option B

4. Quick Check:

   Recursive TrieNode without Box = compile error [OK]

Hint: Rust recursive structs require Box or Rc for children [OK]

Common Mistakes:

• Assuming prefix must be a complete word
• Confusing is_end with prefix existence
• Ignoring Rust recursive type size requirements

4. The following Rust code attempts to use a HashMap for prefix matching but has a bug. What is the bug?

use std::collections::HashMap;

fn main() {
    let mut map = HashMap::new();
    map.insert("apple", 1);
    map.insert("app", 2);

    let prefix = "ap";
    let mut found = false;
    for key in map.keys() {
        if key.starts_with(prefix) {
            found = true;
            break;
        }
    }
    println!("{}", found);
}

medium

A. Inefficient prefix search due to linear scan over keys

B. Using &str keys without lifetime causes compilation error

C. HashMap keys are unordered, so starts_with check is invalid

D. No bug; code works correctly for prefix matching

Solution

1. Step 1: Analyze prefix matching approach

   The code scans all keys linearly and checks if they start with the prefix, which works but is inefficient for large data.

2. Step 2: Identify the bug type

   There is no syntax or runtime error, but the approach is inefficient compared to Trie which supports fast prefix queries.

3. Final Answer:

   Inefficient prefix search due to linear scan over keys -> Option A

4. Quick Check:

   Linear scan for prefix = inefficient [OK]

Hint: HashMap needs full key; prefix search requires scanning all keys [OK]

Common Mistakes:

• Thinking code has syntax or runtime errors
• Assuming HashMap keys are ordered
• Ignoring performance implications

5. You need to implement a system in Rust that supports fast insertion and prefix search for millions of words. Which approach is best and why?

// Option A: Use a Trie with HashMap children
// Option B: Use a HashMap storing all words as keys
// Option C: Use a sorted Vec and binary search for prefix
// Option D: Use a LinkedList of words and scan linearly

hard

A. Trie, because it shares prefixes and allows O(k) prefix search where k is prefix length

B. HashMap, because it provides O(1) exact lookup but slow prefix search

C. Sorted Vec, because binary search helps but prefix search needs extra logic

D. LinkedList, because insertion is fast but prefix search is very slow

Solution

1. Step 1: Evaluate insertion and prefix search efficiency

   Trie allows insertion and prefix search in O(k) time, where k is prefix length, by sharing common prefixes.

2. Step 2: Compare other data structures

   HashMap is fast for exact keys but slow for prefix search. Sorted Vec requires complex prefix range search. LinkedList is slow for prefix search.

3. Final Answer:

   Trie, because it shares prefixes and allows O(k) prefix search where k is prefix length -> Option A

4. Quick Check:

   Fast prefix search = Trie [OK]

Hint: Prefix search speed depends on prefix length, Trie is best [OK]

Common Mistakes:

• Choosing HashMap for prefix search
• Ignoring complexity of prefix range search in sorted Vec
• Underestimating LinkedList search cost