Autocomplete System with Trie in DSA C++ - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to declare the root node of the Trie.

DSA C++

struct TrieNode {
    TrieNode* children[26];
    bool isEndOfWord;

    TrieNode() {
        for (int i = 0; i < 26; i++) {
            children[i] = nullptr;
        }
        isEndOfWord = false;
    }
};

TrieNode* [1] = new TrieNode();

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

Aroot

Bnode

Chead

Dstart

Attempts:

3 left

💡 Hint

Common Mistakes

Using variable names that do not clearly represent the root node.

Not initializing the root node properly.

The root of the Trie is commonly named 'root' to represent the starting point of the Trie structure.

2fill in blank

medium

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

DSA C++

void insertWord(TrieNode* root, const string& word) {
    TrieNode* current = root;
    for (char c : word) {
        int index = c - 'a';
        if (current->children[[1]] == nullptr) {
            current->children[index] = new TrieNode();
        }
        current = current->children[index];
    }
    current->isEndOfWord = true;
}

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

Ac

Bindex

C0

Dword

Attempts:

3 left

💡 Hint

Common Mistakes

Using the character 'c' directly as an index.

Using a fixed index like 0 instead of the calculated index.

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

3fill in blank

hard

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

DSA C++

bool searchWord(TrieNode* root, const string& word) {
    TrieNode* current = root;
    for (char c : word) {
        int index = c - 'a';
        if (current->children[[1]] == nullptr) {
            return false;
        }
        current = current->children[index];
    }
    return current->isEndOfWord;
}

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

Ac

B0

Cindex

Dword

Attempts:

3 left

💡 Hint

Common Mistakes

Checking children[c] instead of children[index].

Using a fixed index like 0.

The search must check the children array at the position given by index, which corresponds to the character c.

4fill in blank

hard

Fill both blanks to complete the recursive function that collects all words starting from a given Trie node.

DSA C++

void collectWords(TrieNode* node, string prefix, vector<string>& results) {
    if (node->[1]) {
        results.push_back(prefix);
    }
    for (int i = 0; i < 26; i++) {
        if (node->children[i] != nullptr) {
            collectWords(node->children[i], prefix + [2], results);
        }
    }
}

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

AisEndOfWord

B'a' + i

Cchar('a' + i)

Dchildren

Attempts:

3 left

💡 Hint

Common Mistakes

Using the wrong member name for the end of word flag.

Appending an integer instead of a character to the prefix.

The function checks if the current node marks the end of a word using isEndOfWord, and appends the character corresponding to index i by converting 'a' + i to a char.

5fill in blank

hard

Fill both blanks to complete the autocomplete function that returns all words with a given prefix.

DSA C++

vector<string> autocomplete(TrieNode* root, const string& prefix) {
    TrieNode* current = root;
    for (char c : prefix) {
        int index = c - 'a';
        if (current->children[[1]] == nullptr) {
            return {};
        }
        current = current->children[index];
    }
    vector<string> results;
    collectWords(current, [2], results);
    return results;
}

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

Aindex

Bprefix

C""

Dcurrent

Attempts:

3 left

💡 Hint

Common Mistakes

Using the wrong index to access children.

Passing an empty string instead of the prefix to collectWords.

Returning the wrong variable.

The function uses the index to traverse children, passes the prefix string to collectWords to start collecting words, and returns the results vector.