Test: Tries - 2 - Software Development MCQ

Which of the following problems can be efficiently solved using TRIE?

What will be the output of the following code snippet?
#include <iostream>
#include <unordered_map>

struct TrieNode {
    std::unordered_map<char, TrieNode*> children;
    bool isEndOfWord;
};

int main() {
    TrieNode* root = new TrieNode();
    root->children['a'] = new TrieNode();
    root->children['b'] = new TrieNode();
    root->children['a']->children['c'] = new TrieNode();
    root->children['a']->children['c']->isEndOfWord = true;
    root->children['b']->children['d'] = new TrieNode();
    root->children['b']->children['d']->isEndOfWord = true;
    std::cout << (root->children['a']->children['c']->isEndOfWord ? "True" : "False") << std::endl;
    std::cout << (root->children['b']->children['d']->isEndOfWord ? "True" : "False") << std::endl;
    delete root;
    return 0;
}

What will be the output of the following code snippet?
#include <iostream>
#include <unordered_map>

struct TrieNode {
    std::unordered_map<char, TrieNode*> children;
    bool isEndOfWord;
};

void insert(TrieNode* root, std::string word) {
    TrieNode* current = root;
    for (char ch : word) {
        if (current->children.find(ch) == current->children.end()) {
            current->children[ch] = new TrieNode();
        }
        current = current->children[ch];
    }
    current->isEndOfWord = true;
}

bool search(TrieNode* root, std::string word) {
    TrieNode* current = root;
    for (char ch : word) {
        if (current->children.find(ch) == current->children.end()) {
            return false;
        }
        current = current->children[ch];
    }
    return current->isEndOfWord;
}

int main() {
    TrieNode* root = new TrieNode();
    insert(root, "hello");
    insert(root, "world");
    std::cout << (search(root, "hello") ? "True" : "False") << std::endl;
    std::cout << (search(root, "world") ? "True" : "False") << std::endl;
    std::cout << (search(root, "bye") ? "True" : "False") << std::endl;
    delete root;
    return 0;
}

What will be the output of the following code snippet?
#include <iostream>
#include <unordered_map>

struct TrieNode {
    std::unordered_map<char, TrieNode*> children;
    bool isEndOfWord;
};

void insert(TrieNode* root, std::string word) {
    TrieNode* current = root;
    for (char ch : word) {
        if (current->children.find(ch) == current->children.end()) {
            current->children[ch] = new TrieNode();
        }
        current = current->children[ch];
    }
    current->isEndOfWord = true;
}

bool deleteWord(TrieNode* root, std::string word, int index) {
    if (index == word.length()) {
        if (!root->isEndOfWord)
            return false;
        root->isEndOfWord = false;
        return root->children.empty();
    }

    char ch = word[index];
    if (root->children.find(ch) == root->children.end())
        return false;

    TrieNode* childNode = root->children[ch];
    bool shouldDeleteCurrentNode = deleteWord(childNode, word, index + 1);

    if (shouldDeleteCurrentNode) {
        root->children.erase(ch);
        delete childNode;
        return root->children.empty();
    }

    return false;
}

int main() {
    TrieNode* root = new TrieNode();
    insert(root, "hello");
    insert(root, "world");
    deleteWord(root, "hello", 0);
    std::cout << (search(root, "hello") ? "True" : "False") << std::endl;
    delete root;
    return 0;
}

What will be the output of the following code snippet?
#include <iostream>
#include <unordered_map>

struct TrieNode {
    std::unordered_map<char, TrieNode*> children;
    bool isEndOfWord;
};

void insert(TrieNode* root, std::string word) {
    TrieNode* current = root;
    for (char ch : word) {
        if (current->children.find(ch) == current->children.end()) {
            current->children[ch] = new TrieNode();
        }
        current = current->children[ch];
    }
    current->isEndOfWord = true;
}

void weightedPrefixSearch(TrieNode* root, std::string prefix, int weight) {
    if (root == nullptr)
        return;

    if (root->isEndOfWord) {
        std::cout << prefix << " (Weight: " << weight << ")" << std::endl;
    }

    for (auto& pair : root->children) {
        char ch = pair.first;
        TrieNode* childNode = pair.second;
        weightedPrefixSearch(childNode, prefix + ch, weight + ch - 'a' + 1);
    }
}

int main() {
    TrieNode* root = new TrieNode();
    insert(root, "apple");
    insert(root, "banana");
    insert(root, "cherry");
    insert(root, "cat");
    weightedPrefixSearch(root, "", 0);
    delete root;
    return 0;
}

What will be the output of the following code snippet?
#include <iostream>
#include <unordered_map>

struct TrieNode {
    std::unordered_map<char, TrieNode*> children;
    bool isEndOfWord;
};

void insert(TrieNode* root, std::string word) {
    TrieNode* current = root;
    for (char ch : word) {
        if (current->children.find(ch) == current->children.end()) {
            current->children[ch] = new TrieNode();
        }
        current = current->children[ch];
    }
    current->isEndOfWord = true;
}

int countWords(TrieNode* root) {
    int count = 0;
    if (root->isEndOfWord)
        count++;

    for (auto& pair : root->children) {
        TrieNode* childNode = pair.second;
        count += countWords(childNode);
    }

    return count;
}

int main() {
    TrieNode* root = new TrieNode();
    insert(root, "hello");
    insert(root, "world");
    std::cout << countWords(root) << std::endl;
    delete root;
    return 0;
}

What will be the output of the following code snippet?
#include <iostream>
#include <unordered_map>

struct TrieNode {
    std::unordered_map<char, TrieNode*> children;
    bool isEndOfWord;
};

void insert(TrieNode* root, std::string word) {
    TrieNode* current = root;
    for (char ch : word) {
        if (current->children.find(ch) == current->children.end()) {
            current->children[ch] = new TrieNode();
        }
        current = current->children[ch];
    }
    current->isEndOfWord = true;
}

bool hasChildren(TrieNode* root) {
    return !root->children.empty();
}

bool deleteHelper(TrieNode* root, std::string word, int index) {
    if (index == word.length()) {
        if (!root->isEndOfWord)
            return false;
        root->isEndOfWord = false;
        return !hasChildren(root);
    }

    char ch = word[index];
    if (root->children.find(ch) == root->children.end())
        return false;

    TrieNode* childNode = root->children[ch];
    bool shouldDeleteCurrentNode = deleteHelper(childNode, word, index + 1);

    if (shouldDeleteCurrentNode) {
        root->children.erase(ch);
        delete childNode;
        return !hasChildren(root);
    }

    return false;
}

bool deleteWord(TrieNode* root, std::string word) {
    return deleteHelper(root, word, 0);
}

int main() {
    TrieNode* root = new TrieNode();
    insert(root, "hello");
    insert(root, "world");
    deleteWord(root, "hello");
    std::cout << countWords(root) << std::endl;
    delete root;
    return 0;
}

What will be the output of the following code snippet?
#include <iostream>
#include <unordered_map>

struct TrieNode {
    std::unordered_map<char, TrieNode*> children;
    bool isEndOfWord;
};

void insert(TrieNode* root, std::string word) {
    TrieNode* current = root;
    for (char ch : word) {
        if (current->children.find(ch) == current->children.end()) {
            current->children[ch] = new TrieNode();
        }
        current = current->children[ch];
    }
    current->isEndOfWord = true;
}

void printWords(TrieNode* root, std::string prefix) {
    if (root->isEndOfWord)
        std::cout << prefix << std::endl;

    for (auto& pair : root->children) {
        char ch = pair.first;
        TrieNode* childNode = pair.second;
        printWords(childNode, prefix + ch);
    }
}

int main() {
    TrieNode* root = new TrieNode();
    insert(root, "apple");
    insert(root, "banana");
    insert(root, "cherry");
    insert(root, "cat");
    printWords(root, "");
    delete root;
    return 0;
}

What will be the output of the following code snippet?
#include <iostream>
#include <unordered_map>

struct TrieNode {
    std::unordered_map<char, TrieNode*> children;
    bool isEndOfWord;
};

void insert(TrieNode* root, std::string word) {
    TrieNode* current = root;
    for (char ch : word) {
        if (current->children.find(ch) == current->children.end()) {
            current->children[ch] = new TrieNode();
        }
        current = current->children[ch];
    }
    current->isEndOfWord = true;
}

int countPrefixes(TrieNode* root, std::string prefix) {
    int count = 0;
    TrieNode* current = root;
    for (char ch : prefix) {
        if (current->children.find(ch) == current->children.end())
            return 0;
        current = current->children[ch];
        count++;
    }
    return count;
}

int main() {
    TrieNode* root = new TrieNode();
    insert(root, "apple");
    insert(root, "banana");
    insert(root, "cherry");
    insert(root, "cat");
    std::cout << countPrefixes(root, "b") << std::endl;
    std::cout << countPrefixes(root, "ca") << std::endl;
    std::cout << countPrefixes(root, "apx") << std::endl;
    delete root;
    return 0;
}

Which of the following is NOT a step in the Boggle game using TRIE data structure?

In the Boggle game, what is the purpose of a TRIE data structure?

Which of the following is NOT a typical optimization technique used in the Boggle game using TRIE data structure?