Autocomplete System with Trie in DSA Java - Interactive Practice

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'

Aindex

Bc

Cch

Dletter

Attempts:

3 left

💡 Hint

Common Mistakes

Using an integer index instead of the character variable.

Using a variable name that is not defined in the loop.

The variable 'ch' represents the current character being inserted, so we subtract 'a' to get the index.

2fill in blank

medium

Complete the code to check if the current node marks the end of a word.

DSA Java

if (node.[1]) { return true; }

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

AisEnd

BwordEnd

CendOfWord

DisWord

Attempts:

3 left

💡 Hint

Common Mistakes

Using a variable name that does not exist in the TrieNode class.

Confusing the flag with the children array.

The boolean flag 'isEnd' is commonly used to mark the end of a word in a Trie node.

3fill in blank

hard

Fix the error in the search method to correctly traverse the Trie.

DSA Java

node = node.children[[1] - 'a'];

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

Aword.charAt(i + 1)

Bword.charAt(0)

Cword.charAt(i - 1)

Dword.charAt(i)

Attempts:

3 left

💡 Hint

Common Mistakes

Using a fixed index like 0 instead of the loop variable.

Using an index out of bounds like i+1 or i-1.

We use word.charAt(i) to get the current character at index i during traversal.

4fill in blank

hard

Fill both blanks to add a word to the Trie and mark its end.

DSA Java

for (char [1] : word.toCharArray()) {
    if (node.children[[2] - 'a'] == null) {
        node.children[[2] - 'a'] = new TrieNode();
    }
    node = node.children[[2] - 'a'];
}
node.isEnd = true;

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

Ach

Bc

Cletter

Dnode

Attempts:

3 left

💡 Hint

Common Mistakes

Using different variable names for loop and indexing.

Using a variable that is not a character.

The variable 'ch' is used to iterate over characters and index children accordingly.

5fill in blank

hard

Fill all three blanks to implement the autocomplete helper method that collects words.

DSA Java

private void [1](TrieNode node, String prefix, List<String> results) {
    if (node.[2]) {
        results.add(prefix);
    }
    for (int i = 0; i < 26; i++) {
        if (node.children[i] != null) {
            char [3] = (char) (i + 'a');
            [1](node.children[i], prefix + [3], results);
        }
    }
}

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

Adfs

BisEnd

Cch

Dsearch

Attempts:

3 left

💡 Hint

Common Mistakes

Using wrong method name like 'search' instead of 'dfs'.

Using incorrect boolean flag name.

Using a variable name other than 'ch' for characters.

The method is named 'dfs' for depth-first search, checks 'isEnd' flag, and uses 'ch' as the character variable.

Practice

1. What is the main purpose of using a Trie in an autocomplete system?

easy

A. To count the frequency of words

B. To efficiently store and search prefixes of words

C. To sort words alphabetically

D. To encrypt the stored words

Solution

1. Step 1: Understand the role of Trie in prefix search

   A Trie is a tree-like data structure that stores characters of words in a way that common prefixes share nodes.

2. Step 2: Connect Trie usage to autocomplete

   Autocomplete requires quick lookup of words starting with a given prefix, which Trie supports efficiently.

3. Final Answer:

   To efficiently store and search prefixes of words -> Option B

4. Quick Check:

   Trie = prefix search [OK]

Hint: Trie is built for prefix-based fast search [OK]

Common Mistakes:

• Confusing Trie with sorting data structure
• Thinking Trie encrypts data
• Assuming Trie counts word frequency only

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

easy

A. class TrieNode { char[] children = new char[26]; boolean isWord; }

B. class TrieNode { int[] children = new int[26]; boolean isWord; }

C. class TrieNode { String[] children = new String[26]; boolean isWord; }

D. class TrieNode { TrieNode[] children = new TrieNode[26]; boolean isWord; }

Solution

1. Step 1: Identify the correct data type for children nodes

   Each child should be a reference to another TrieNode, so an array of TrieNode objects is needed.

2. Step 2: Check other options for correctness

   Options B, C, and D use primitive types or String arrays which cannot represent child nodes properly.

3. Final Answer:

   class TrieNode { TrieNode[] children = new TrieNode[26]; boolean isWord; } -> Option D

4. Quick Check:

   Children = TrieNode array [OK]

Hint: Children must be TrieNode references, not primitives [OK]

Common Mistakes:

• Using int or char arrays instead of TrieNode array
• Using String array for children
• Forgetting to initialize children array

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

Trie trie = new Trie();
trie.insert("dog");
trie.insert("deer");
trie.insert("deal");
List<String> results = trie.autocomplete("de");
System.out.println(results);

medium

A. ["deer", "deal"]

B. ["dog", "deer", "deal"]

C. ["dog"]

D. []

Solution

1. Step 1: Understand inserted words and prefix search

   Words inserted are "dog", "deer", and "deal". The prefix searched is "de".

2. Step 2: Filter words starting with prefix "de"

   Only "deer" and "deal" start with "de"; "dog" starts with "do".

3. Final Answer:

   ["deer", "deal"] -> Option A

4. Quick Check:

   Autocomplete("de") = ["deer", "deal"] [OK]

Hint: Autocomplete returns words starting exactly with prefix [OK]

Common Mistakes:

• Including words not matching prefix
• Returning empty list by mistake
• Confusing prefix "de" with "do"

4. Identify the bug in this Trie insertion method snippet and select the fix:

public void insert(String word) {
  TrieNode node = root;
  for (int i = 0; i <= word.length(); i++) {
    char c = word.charAt(i);
    int index = c - 'a';
    if (node.children[index] == null) {
      node.children[index] = new TrieNode();
    }
    node = node.children[index];
  }
  node.isWord = true;
}

medium

A. Change loop condition to i < word.length() to avoid IndexOutOfBoundsException

B. Initialize root inside the loop

C. Remove node.isWord assignment

D. Change char c to int c

Solution

1. Step 1: Analyze loop boundary

   The loop runs from i = 0 to i <= word.length(), which causes i to reach word.length(), an invalid index for charAt.

2. Step 2: Fix loop condition

   Changing condition to i < word.length() prevents IndexOutOfBoundsException by stopping before invalid index.

3. Final Answer:

   Change loop condition to i < word.length() to avoid IndexOutOfBoundsException -> Option A

4. Quick Check:

   Loop index < word.length() [OK]

Hint: Loop over string chars with i < length, not <= length [OK]

Common Mistakes:

• Using <= instead of < in loop condition
• Ignoring IndexOutOfBoundsException
• Misunderstanding charAt indexing

5. You want to extend a Trie-based autocomplete system to return suggestions sorted by frequency of word usage. Which data structure modification is best to support this efficiently?

hard

A. Store words in a linked list attached to each node

B. Sort all words alphabetically after each insertion

C. Store a frequency count at each word node and use a priority queue during search

D. Use a hash map to store words and frequencies separately from the Trie

Solution

1. Step 1: Understand frequency tracking in Trie nodes

   Storing frequency count at each word node allows tracking how often each word is used.

2. Step 2: Use priority queue to get top frequent words during autocomplete

   During prefix search, a priority queue can efficiently retrieve words with highest frequency.

3. Final Answer:

   Store a frequency count at each word node and use a priority queue during search -> Option C

4. Quick Check:

   Frequency + priority queue = efficient sorted suggestions [OK]

Hint: Use frequency counts + priority queue for sorted autocomplete [OK]

Common Mistakes:

• Sorting all words after each insertion (inefficient)
• Separating frequency from Trie nodes (loses prefix efficiency)
• Using linked list for sorting (slow access)