Autocomplete System with Trie in DSA C - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to create a new Trie node.

DSA C

TrieNode* createNode() {
    TrieNode* node = (TrieNode*)malloc(sizeof(TrieNode));
    node->isEndOfWord = [1];
    for (int i = 0; i < 26; i++) {
        node->children[i] = NULL;
    }
    return node;
}

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

A0

B1

CNULL

D-1

Attempts:

3 left

💡 Hint

Common Mistakes

Setting isEndOfWord to 1 by mistake, which means the node is end of a word.

Using NULL instead of 0 for a boolean flag.

The isEndOfWord flag should be initialized to 0 (false) when creating a new Trie node.

2fill in blank

medium

Complete the code to insert a character into the Trie children array.

DSA C

void insertChar(TrieNode* node, char c) {
    int index = c - 'a';
    if (node->children[[1]] == NULL) {
        node->children[index] = createNode();
    }
}

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

Ac

Bindex

Cnode

D0

Attempts:

3 left

💡 Hint

Common Mistakes

Using the character c directly as an index.

Using 0 instead of the calculated index.

The index variable holds the position for the character c in the children array.

3fill in blank

hard

Fix the error in the search function to check if a character exists in the Trie.

DSA C

int search(TrieNode* root, const char* word) {
    TrieNode* current = root;
    for (int i = 0; word[i] != '\0'; i++) {
        int index = word[i] - 'a';
        if (current->children[[1]] == NULL) {
            return 0;
        }
        current = current->children[index];
    }
    return current->isEndOfWord;
}

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

Aindex

Bword[i]

Ci

Dcurrent

Attempts:

3 left

💡 Hint

Common Mistakes

Using the character word[i] directly as an index.

Using the loop variable i as index.

We must use the calculated index to check the children array for the character.

4fill in blank

hard

Fill both blanks to implement the recursive function to collect all words from a given Trie node.

DSA C

void collectWords(TrieNode* node, char* prefix, int length, char results[][100], int* count) {
    if (node->isEndOfWord) {
        prefix[length] = '\0';
        strcpy(results[*count], [1]);
        (*count)++;
    }
    for (int i = 0; i < 26; i++) {
        if (node->children[i]) {
            prefix[length] = [2];
            collectWords(node->children[i], prefix, length + 1, results, count);
        }
    }
}

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

Aprefix

B'a' + i

Cresults

Di

Attempts:

3 left

💡 Hint

Common Mistakes

Copying results instead of prefix.

Using i directly as a character instead of 'a' + i.

Copy the current prefix string to results, and add the character 'a' + i to prefix before recursion.

5fill in blank

hard

Fill all three blanks to implement the autocomplete function that returns all words starting with a prefix.

DSA C

void autocomplete(TrieNode* root, const char* prefix, char results[][100], int* count) {
    TrieNode* current = root;
    for (int i = 0; prefix[i] != '\0'; i++) {
        int index = prefix[i] - 'a';
        if (current->children[[1]] == NULL) {
            return;
        }
        current = current->children[index];
    }
    char buffer[100];
    strcpy(buffer, [2]);
    collectWords(current, buffer, [3], results, count);
}

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

Aindex

Bprefix

Cstrlen(prefix)

D0

Attempts:

3 left

💡 Hint

Common Mistakes

Using prefix[i] instead of index to check children.

Passing 0 instead of prefix length to collectWords.

Not copying prefix to buffer before collecting words.

Use index to check children, copy prefix to buffer, and pass prefix length to collectWords.

Practice

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

easy

A. To store words in a tree structure for fast prefix search

B. To sort words alphabetically before searching

C. To store words in a linked list for sequential access

D. To compress words into a hash table for quick lookup

Solution

1. Step 1: Understand the role of Trie in autocomplete

   A Trie stores words character by character in a tree, allowing quick prefix matching.

2. Step 2: Compare with other data structures

   Linked lists and hash tables do not efficiently support prefix searches like Tries do.

3. Final Answer:

   To store words in a tree structure for fast prefix search -> Option A

4. Quick Check:

   Trie = fast prefix search [OK]

Hint: Trie = tree for prefixes, perfect for autocomplete [OK]

Common Mistakes:

• Confusing Trie with hash table
• Thinking linked list is efficient for prefix search
• Assuming sorting alone solves autocomplete

2. Which of the following is the correct way to declare a Trie node structure in C for lowercase English letters?

easy

A. typedef struct TrieNode { struct TrieNode* children[26]; int isEndOfWord; } TrieNode;

B. typedef struct TrieNode { struct TrieNode* children[52]; int isEndOfWord; } TrieNode;

C. typedef struct TrieNode { struct TrieNode* children[10]; int isEndOfWord; } TrieNode;

D. typedef struct TrieNode { struct TrieNode* children; int isEndOfWord; } TrieNode;

Solution

1. Step 1: Identify the size of children array for lowercase letters

   There are 26 lowercase English letters, so children array size should be 26.

2. Step 2: Check the structure correctness

   Each node has an array of pointers to children and a flag for end of word.

3. Final Answer:

   typedef struct TrieNode { struct TrieNode* children[26]; int isEndOfWord; } TrieNode; -> Option A

4. Quick Check:

   26 children for lowercase letters [OK]

Hint: 26 children pointers for lowercase English letters [OK]

Common Mistakes:

• Using 52 for uppercase + lowercase without clarification
• Using 10 for digits only
• Not using array for children pointers

3. Given the following code snippet inserting words into a Trie and searching for prefix "app":

insert("apple");
insert("app");
insert("application");
searchPrefix("app");

What will searchPrefix("app") return?

medium

A. ["app"]

B. ["app", "apple", "application"]

C. ["apple", "application"]

D. []

Solution

1. Step 1: Understand insertion of words

   Words "apple", "app", and "application" are inserted, all sharing prefix "app".

2. Step 2: Search prefix "app" returns all words starting with "app"

   So, it returns all three words: "app", "apple", and "application".

3. Final Answer:

   ["app", "apple", "application"] -> Option B

4. Quick Check:

   Prefix "app" matches 3 words [OK]

Hint: Prefix search returns all words starting with prefix [OK]

Common Mistakes:

• Returning only exact matches
• Missing shorter word "app"
• Returning empty list incorrectly

4. Consider this buggy C code snippet for inserting a word into a Trie:

void insert(TrieNode* root, const char* word) {
  TrieNode* node = root;
  for (int i = 0; word[i] != '\0'; i++) {
    int index = word[i] - 'a';
    if (node->children[index] == NULL) {
      node->children[index] = malloc(sizeof(TrieNode));
      memset(node->children[index], 0, sizeof(TrieNode));
    }
    node = node->children[index];
  }
  node->isEndOfWord = 1;
}

What is the main bug in this code?

medium

A. Root node is not checked for NULL

B. Index calculation is incorrect

C. isEndOfWord is set before loop

D. New nodes are not initialized after malloc

Solution

1. Step 1: Analyze malloc usage for new nodes

   malloc allocates memory but does not initialize children pointers or isEndOfWord flag.

2. Step 2: Consequence of missing initialization

   Uninitialized children pointers may cause undefined behavior during traversal or insertion.

3. Final Answer:

   New nodes are not initialized after malloc -> Option D

4. Quick Check:

   malloc needs initialization [OK]

Hint: Always initialize new Trie nodes after malloc [OK]

Common Mistakes:

• Assuming malloc zeroes memory
• Thinking index calculation is wrong
• Ignoring initialization of isEndOfWord

5. You want to extend a Trie-based autocomplete system to support case-insensitive search for English letters (both uppercase and lowercase). Which modification is the best approach?

hard

A. Store words as-is and compare characters ignoring case during search only

B. Increase children array size to 52 to store uppercase and lowercase separately

C. Convert all input words to lowercase before insertion and search, keep children array size 26

D. Use a hash map instead of array for children to store any character

Solution

1. Step 1: Consider memory and complexity

   Using 52 children doubles memory; hash map adds overhead; ignoring case only during search is inefficient.

2. Step 2: Normalize input for simplicity

   Converting all words to lowercase before insertion and search simplifies Trie structure and ensures consistent matching.

3. Final Answer:

   Convert all input words to lowercase before insertion and search, keep children array size 26 -> Option C

4. Quick Check:

   Normalize case before Trie operations [OK]

Hint: Normalize case before insert/search for simpler Trie [OK]

Common Mistakes:

• Doubling children array size unnecessarily
• Ignoring case only during search causes mismatch
• Using hash map adds complexity and overhead