Count Words with Given Prefix in DSA C++ - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of prefix count after insertions

What is the output of the following C++ code that inserts words into a prefix count structure and queries the count for prefix "app"?

DSA C++

class TrieNode {
public:
    int count = 0;
    TrieNode* children[26] = {nullptr};
};

class Trie {
public:
    TrieNode* root;
    Trie() { root = new TrieNode(); }
    void insert(const std::string& word) {
        TrieNode* node = root;
        for (char c : word) {
            int idx = c - 'a';
            if (!node->children[idx]) node->children[idx] = new TrieNode();
            node = node->children[idx];
            node->count++;
        }
    }
    int countPrefix(const std::string& prefix) {
        TrieNode* node = root;
        for (char c : prefix) {
            int idx = c - 'a';
            if (!node->children[idx]) return 0;
            node = node->children[idx];
        }
        return node->count;
    }
};

int main() {
    Trie trie;
    trie.insert("apple");
    trie.insert("app");
    trie.insert("application");
    trie.insert("apt");
    std::cout << trie.countPrefix("app") << std::endl;
    return 0;
}

A 4

B 3

C 2

D 1

💡 Hint

Count how many inserted words start with "app".

The words inserted are "apple", "app", "application", and "apt".

Only "apple", "app", and "application" start with "app".

So the count for prefix "app" is 3.

❓ Predict Output

intermediate

Count prefix with no matching words

What will be the output of the code when counting prefix "bat" after inserting words "cat", "car", "cart"?

DSA C++

class TrieNode {
public:
    int count = 0;
    TrieNode* children[26] = {nullptr};
};

class Trie {
public:
    TrieNode* root;
    Trie() { root = new TrieNode(); }
    void insert(const std::string& word) {
        TrieNode* node = root;
        for (char c : word) {
            int idx = c - 'a';
            if (!node->children[idx]) node->children[idx] = new TrieNode();
            node = node->children[idx];
            node->count++;
        }
    }
    int countPrefix(const std::string& prefix) {
        TrieNode* node = root;
        for (char c : prefix) {
            int idx = c - 'a';
            if (!node->children[idx]) return 0;
            node = node->children[idx];
        }
        return node->count;
    }
};

int main() {
    Trie trie;
    trie.insert("cat");
    trie.insert("car");
    trie.insert("cart");
    std::cout << trie.countPrefix("bat") << std::endl;
    return 0;
}

A 0

B 1

C 3

D 2

💡 Hint

Check if any inserted word starts with "bat".

None of the inserted words "cat", "car", "cart" start with "bat".

So the count for prefix "bat" is 0.

🔧 Debug

advanced

Identify the error in prefix count code

What error will the following code produce when counting prefix "app" after inserting "apple" and "app"?

DSA C++

class TrieNode {
public:
    int count = 0;
    TrieNode* children[26];
    TrieNode() {
        for (int i = 0; i < 26; i++) children[i] = nullptr;
    }
};

class Trie {
public:
    TrieNode* root;
    Trie() { root = new TrieNode(); }
    void insert(const std::string& word) {
        TrieNode* node = root;
        for (char c : word) {
            int idx = c - 'a';
            if (!node->children[idx]) node->children[idx] = new TrieNode();
            node = node->children[idx];
            node->count++;
        }
    }
    int countPrefix(const std::string& prefix) {
        TrieNode* node = root;
        for (char c : prefix) {
            int idx = c - 'a';
            if (!node->children[idx]) return 0;
            node = node->children[idx];
        }
        return node->count;
    }
};

int main() {
    Trie trie;
    trie.insert("apple");
    trie.insert("app");
    std::cout << trie.countPrefix("app") << std::endl;
    return 0;
}

A Compilation error: uninitialized array

B Runtime error: segmentation fault

C No error, output is 2

D Output is 0

💡 Hint

Check if children array is initialized properly.

The children array is initialized to nullptr in the constructor, so no segmentation fault occurs.

The count increments correctly for "apple" and "app".

Output is 2 because two words start with "app".

🧠 Conceptual

advanced

Understanding prefix count updates in Trie

If you insert the words "dog", "door", "dorm", and then delete "door" from a Trie that counts prefixes, what should happen to the prefix counts for "do"?

A The count for prefix "do" remains the same

B The count for prefix "do" becomes zero

C The count for prefix "do" decreases by 2

D The count for prefix "do" decreases by 1

💡 Hint

Deleting one word that starts with "do" affects counts accordingly.

Initially, three words start with "do": "dog", "door", "dorm".

Deleting "door" removes one word starting with "do".

So the count for prefix "do" decreases by 1.

🚀 Application

expert

Find number of words with prefix after multiple insertions

Given the following sequence of insertions into a prefix counting Trie: "test", "tester", "testing", "team", "teach", what is the count of words with prefix "te"?

A 5

B 3

C 2

D 4

💡 Hint

Count all words starting with "te".

The words are "test", "tester", "testing", "team", "teach".

All start with "te" including "team" and "teach".

So total 5 words start with "te".

But the question asks for count of words with prefix "te" which is 5.

Wait, options do not have 5 as correct answer except A.

Check carefully: all 5 start with "te".

So correct answer is 5 (option A).