Autocomplete System with Trie in DSA Java - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Trie Insertion and Search

What is the output of the following Java code that inserts words into a Trie and searches for a prefix?

DSA Java

class TrieNode {
    TrieNode[] children = new TrieNode[26];
    boolean isEnd = false;
}

class Trie {
    TrieNode root = new TrieNode();

    void insert(String word) {
        TrieNode node = root;
        for (char c : word.toCharArray()) {
            int idx = c - 'a';
            if (node.children[idx] == null) {
                node.children[idx] = new TrieNode();
            }
            node = node.children[idx];
        }
        node.isEnd = true;
    }

    boolean startsWith(String prefix) {
        TrieNode node = root;
        for (char c : prefix.toCharArray()) {
            int idx = c - 'a';
            if (node.children[idx] == null) return false;
            node = node.children[idx];
        }
        return true;
    }
}

public class Main {
    public static void main(String[] args) {
        Trie trie = new Trie();
        trie.insert("apple");
        trie.insert("app");
        System.out.println(trie.startsWith("app"));
        System.out.println(trie.startsWith("apl"));
    }
}

A

false
false

B

true
false

C

true
true

D

false
true

💡 Hint

Check if the prefix exists in the Trie after inserting the words.

The prefix "app" exists because both "app" and "apple" were inserted. The prefix "apl" does not exist in the Trie, so startsWith returns false.

🧠 Conceptual

intermediate

Understanding Trie Node Structure

Which of the following best describes the structure of a Trie node used in an autocomplete system?

A A node contains an array of child nodes for each letter and a boolean indicating if it is the end of a word.

B A node contains a hash map of all words in the Trie.

C A node contains a pointer to the parent node and a count of words passing through it.

D A node contains only a list of words that start with the prefix up to that node.

💡 Hint

Think about how each character leads to the next in a Trie.

Each Trie node typically has an array (or map) of child nodes for each possible character and a boolean flag to mark if a word ends at that node.

🔧 Debug

advanced

Identify the Error in Trie Search Method

What error will the following Java method cause when searching for a word in a Trie?

DSA Java

boolean search(String word) {
    TrieNode node = root;
    for (int i = 0; i < word.length(); i++) {
        int idx = word.charAt(i) - 'a';
        if (node.children[idx] == null) return false;
        node = node.children[idx];
    }
    return node.isEnd;
}

A Returns false even if word exists

B NullPointerException

C StringIndexOutOfBoundsException

D Compiles but never returns

💡 Hint

Check the loop boundary condition carefully.

The loop uses i <= word.length(), which causes an index out of bounds when i equals word.length().

🚀 Application

advanced

Autocomplete Suggestions Using Trie

Given a Trie with inserted words, which method correctly collects all words starting with a given prefix?

DSA Java

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

A Collect words by breadth-first search without recursion.

B Iterate only over children with isEnd true, ignoring others.

C Add prefix to results only if node has no children.

D Recursively traverse children, adding words when isEnd is true.

💡 Hint

Think about how to explore all possible continuations of the prefix.

The method recursively explores all children nodes, adding words when the end of a word is reached.

❓ Predict Output

expert

Output of Autocomplete System with Multiple Insertions

What is the output of the following Java code that inserts words and prints autocomplete suggestions for prefix "ca"?

DSA Java

import java.util.*;

class TrieNode {
    TrieNode[] children = new TrieNode[26];
    boolean isEnd = false;
}

class Trie {
    TrieNode root = new TrieNode();

    void insert(String word) {
        TrieNode node = root;
        for (char c : word.toCharArray()) {
            int idx = c - 'a';
            if (node.children[idx] == null) {
                node.children[idx] = new TrieNode();
            }
            node = node.children[idx];
        }
        node.isEnd = true;
    }

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

    List<String> autocomplete(String prefix) {
        TrieNode node = root;
        for (char c : prefix.toCharArray()) {
            int idx = c - 'a';
            if (node.children[idx] == null) return new ArrayList<>();
            node = node.children[idx];
        }
        List<String> results = new ArrayList<>();
        collectWords(node, prefix, results);
        return results;
    }
}

public class Main {
    public static void main(String[] args) {
        Trie trie = new Trie();
        trie.insert("cat");
        trie.insert("car");
        trie.insert("cart");
        trie.insert("dog");
        List<String> suggestions = trie.autocomplete("ca");
        System.out.println(suggestions);
    }
}

A [car, cart, cat]

B [car, cat]

C [cat, cart, car]

D [cat, car, cart]

💡 Hint

Check the order in which children are traversed in collectWords.

The collectWords method traverses children from index 0 to 25, which corresponds to 'a' to 'z'. So 'car' (c-a-r) is found before 'cart' (c-a-r-t) and 'cat' (c-a-t) because 'r' < 't' in ASCII. The correct lex order is 'car', 'cart', 'cat'.

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)