Why Trie Exists and What Hash Map Cannot Do for Strings in DSA Java - Test Your Knowledge

Practice - 5 Tasks

1fill in blank

easy

Complete the code to insert a character into the Trie node's children.

DSA Java

node.children[[1] - 'a'] = new TrieNode();

Drag options to blanks, or click blank then click option'

Ach

Bc

Cindex

Di

Attempts:

3 left

💡 Hint

Common Mistakes

Using loop index 'i' instead of character 'ch'.

Using variable 'index' which is undefined.

We use 'ch' as the character to find the correct index in children array.

2fill in blank

medium

Complete the code to check if a prefix exists in the Trie.

DSA Java

if (node.children[[1] - 'a'] == null) return false;

Drag options to blanks, or click blank then click option'

Ai

Bindex

Cc

Dch

Attempts:

3 left

💡 Hint

Common Mistakes

Using loop index 'i' instead of character 'ch'.

Using undefined variable 'index'.

We check the child node corresponding to character 'ch'.

3fill in blank

hard

Fix the error in the code to mark the end of a word in the Trie.

DSA Java

node.[1] = true;

Drag options to blanks, or click blank then click option'

AisEndOfWord

BwordEnd

Cend

DisWord

Attempts:

3 left

💡 Hint

Common Mistakes

Using variable names that do not exist in the TrieNode class.

Using 'end' or 'wordEnd' which are not standard.

The standard boolean flag to mark word end is 'isEndOfWord'.

4fill in blank

hard

Fill both blanks to complete the Trie search method for a word.

DSA Java

for (char [1] : word.toCharArray()) {
    if (node.children[[2] - 'a'] == null) return false;
    node = node.children[[2] - 'a'];
}

Drag options to blanks, or click blank then click option'

Ach

Bc

Ci

Dindex

Attempts:

3 left

💡 Hint

Common Mistakes

Using different variable names for loop and index.

Using loop index 'i' which is not defined in this loop.

The loop variable and index use the same character 'ch' to access children.

5fill in blank

hard

Fill all three blanks to create a map comprehension that counts characters in a string.

DSA Java

Map<Character, Integer> counts = new HashMap<>();
for (char [1] : word.toCharArray()) {
    counts.put([2], counts.getOrDefault([3], 0) + 1);
}

Drag options to blanks, or click blank then click option'

Ach

Dc

Attempts:

3 left

💡 Hint

Common Mistakes

Using different variable names causing errors.

Using undefined variables in map methods.

Use 'ch' consistently to count each character's frequency in the map.

Practice

1. Why do we use a Trie data structure instead of a Hash Map for storing a large set of strings?

easy

A. Because Trie efficiently supports prefix-based searches which Hash Map cannot do directly

B. Because Trie uses less memory than Hash Map for all data types

C. Because Hash Map cannot store strings as keys

D. Because Trie automatically sorts strings alphabetically

Solution

1. Step 1: Understand Trie and Hash Map capabilities

   Trie stores strings in a tree form where each node represents a character, enabling prefix searches. Hash Map stores key-value pairs but does not support prefix queries efficiently.

2. Step 2: Compare prefix search support

   Trie can quickly find all strings starting with a prefix by traversing nodes. Hash Map requires checking each key individually, which is inefficient.

3. Final Answer:

   Because Trie efficiently supports prefix-based searches which Hash Map cannot do directly -> Option A

4. Quick Check:

   Prefix search = Trie advantage [OK]

Hint: Trie is for prefix search; Hash Map is not [OK]

Common Mistakes:

• Thinking Hash Map can do prefix search efficiently
• Assuming Trie uses less memory always
• Believing Hash Map cannot store strings as keys

2. Which of the following is the correct way to declare a Trie node class in Java?

easy

A. class TrieNode { int[] children = new int[26]; boolean isEndOfWord; }

B. class TrieNode { List<String> children; boolean isEndOfWord; }

C. class TrieNode { String children; boolean isEndOfWord; }

D. class TrieNode { Map children = new HashMap<>(); boolean isEndOfWord; }

Solution

1. Step 1: Identify correct data type for children

   Trie node children should map characters to next nodes, so Map is correct.

2. Step 2: Check other options

   class TrieNode { int[] children = new int[26]; boolean isEndOfWord; } uses int array which is possible but not a Map; class TrieNode { String children; boolean isEndOfWord; } uses String which is incorrect; class TrieNode { List<String> children; boolean isEndOfWord; } uses List<String> which is not suitable for child nodes.

3. Final Answer:

   class TrieNode { Map children = new HashMap<>(); boolean isEndOfWord; } -> Option D

4. Quick Check:

   Children map = class TrieNode { Map children = new HashMap<>(); boolean isEndOfWord; } [OK]

Hint: Trie children map chars to nodes [OK]

Common Mistakes:

• Using String or List instead of Map for children
• Using int array without explanation
• Forgetting isEndOfWord boolean

3. What will be the output of the following Java code snippet using a Trie?

Trie trie = new Trie();
trie.insert("apple");
trie.insert("app");
System.out.println(trie.startsWith("app"));
System.out.println(trie.search("apple"));
System.out.println(trie.search("apples"));

medium

A. true false true

B. false true false

C. true true false

D. false false false

Solution

1. Step 1: Understand insert and search operations

   Inserting "apple" and "app" adds both words. startsWith("app") checks if any word starts with "app" which is true. search("apple") finds exact word, true. search("apples") not inserted, false.

2. Step 2: Evaluate each print statement

   startsWith("app") -> true; search("apple") -> true; search("apples") -> false.

3. Final Answer:

   true true false -> Option C

4. Quick Check:

   Insert + search + prefix check = true true false [OK]

Hint: startsWith true if prefix exists, search true if exact word [OK]

Common Mistakes:

• Confusing startsWith and search results
• Assuming search("apples") returns true
• Mixing order of outputs

4. The following Java code tries to insert strings into a Trie but throws a NullPointerException. What is the likely cause?

class TrieNode {
  Map children;
  boolean isEndOfWord;
}

class Trie {
  TrieNode root = new TrieNode();
  public void insert(String word) {
    TrieNode node = root;
    for (char c : word.toCharArray()) {
      if (!node.children.containsKey(c)) {
        node.children.put(c, new TrieNode());
      }
      node = node.children.get(c);
    }
    node.isEndOfWord = true;
  }
}

medium

A. children map is not initialized in TrieNode constructor

B. root node is not initialized

C. word.toCharArray() returns null

D. isEndOfWord is not set to false initially

Solution

1. Step 1: Identify NullPointerException source

   NullPointerException likely occurs when calling node.children.containsKey(c) because children map is null.

2. Step 2: Check initialization of children map

   TrieNode class declares children but does not initialize it (e.g., new HashMap<>()), so children is null causing exception.

3. Final Answer:

   children map is not initialized in TrieNode constructor -> Option A

4. Quick Check:

   Uninitialized map = NullPointerException [OK]

Hint: Always initialize children map in TrieNode [OK]

Common Mistakes:

• Assuming root is null
• Thinking toCharArray() returns null
• Ignoring map initialization

5. You want to store a dictionary of 1 million English words and efficiently find all words starting with a given prefix. Why is a Trie better than a Hash Map for this task, and what is a key limitation of Hash Map here?

hard

A. Trie automatically sorts words; Hash Map does not support string keys

B. Trie stores words in a prefix tree allowing fast prefix queries; Hash Map cannot efficiently find keys by prefix without checking all keys

C. Trie uses less memory than Hash Map for large datasets; Hash Map keys must be integers

D. Trie supports deletion of words in O(1); Hash Map deletion is O(n)

Solution

1. Step 1: Understand prefix search requirement

   Finding all words starting with a prefix requires efficient prefix queries, which Trie supports by traversing nodes matching prefix characters.

2. Step 2: Analyze Hash Map limitation

   Hash Map stores keys without order or structure, so to find keys by prefix, it must check all keys, which is slow for large datasets.

3. Final Answer:

   Trie stores words in a prefix tree allowing fast prefix queries; Hash Map cannot efficiently find keys by prefix without checking all keys -> Option B

4. Quick Check:

   Prefix search efficiency = Trie advantage [OK]

Hint: Trie = prefix search; Hash Map = no prefix search [OK]

Common Mistakes:

• Thinking Hash Map keys must be integers
• Assuming Trie uses less memory always
• Confusing deletion complexities