Open App

All Exams > Software Development > DSA in C++ > All Questions

All questions of Tries for Software Development Exam

The time complexity for searching a string in a Trie of N nodes is:
a)
O(1)
b)
O(log N)
c)
O(N)
d)
O(M), where M is the length of the searched string
Correct answer is option 'D'. Can you explain this answer?

Ritesh Kumar Shivhare answered

The time complexity for searching a string in a Trie is proportional to the length of the searched string. It requires traversing the Trie from the root to the leaf node corresponding to the last character of the string.

View Answers

1 Crore+ students have signed up on EduRev. Have you? Download the App

Which operation is NOT typically performed on a TRIE?
a)
Insertion
b)
Deletion
c)
Sorting
d)
Search
Correct answer is option 'C'. Can you explain this answer?

Prateek Yadav answered

Introduction:
A Trie (also known as a prefix tree) is a tree-like data structure used for efficient retrieval of keys in a large set of strings. It is particularly useful in scenarios where we need to store and search for strings efficiently. The Trie data structure has several operations, including insertion, deletion, search, and sorting. However, the operation that is not typically performed on a Trie is sorting.

Explanation:
1. Insertion:
Insertion is one of the fundamental operations of a Trie. It involves adding a new key (string) to the existing Trie. Insertion in a Trie is efficient and has a time complexity of O(L), where L is the length of the key being inserted. During insertion, the Trie is modified by creating new nodes and updating the existing ones to represent the added key.

2. Deletion:
Deletion is another important operation performed on a Trie. It involves removing a key from the Trie. Deletion in a Trie is also efficient and has a time complexity of O(L), where L is the length of the key being deleted. During deletion, the Trie is modified by removing nodes and updating the existing ones to maintain the structure of the Trie.

3. Search:
Search is a common operation performed on a Trie. It involves finding whether a given key exists in the Trie or not. Searching in a Trie is efficient and has a time complexity of O(L), where L is the length of the key being searched. During search, the Trie is traversed from the root to the leaf nodes, comparing each character of the key with the characters stored in the Trie.

4. Sorting:
Unlike the other operations mentioned above, sorting is not typically performed on a Trie. The primary purpose of a Trie is to store and retrieve keys efficiently, rather than sorting them. Sorting involves arranging the keys in a specific order (e.g., lexicographically) based on some criteria. While it is possible to sort the keys stored in a Trie, it is not a natural or common operation performed on a Trie.

Conclusion:
In summary, the operation that is not typically performed on a Trie is sorting. Trie data structure is primarily used for efficient insertion, deletion, and searching of keys. Although sorting can be achieved using a Trie, it is not a common use case for Trie data structure.

View Answers

Which of the following operations is NOT typically supported by a Trie?
a)
Insertion of a string
b)
Deletion of a string
c)
Search for a string
d)
Sorting the strings in lexicographic order
Correct answer is option 'D'. Can you explain this answer?

Ritesh Kumar Shivhare answered

Although it is possible to retrieve strings from a Trie in lexicographic order, it is not a typical operation supported by Tries. The main operations supported by Tries are insertion, search, and prefix matching.

View Answers

Given a Trie data structure and a list of strings, how can you efficiently find the longest duplicate substring in the list? Implement the 'longestDuplicateSubstring' function that returns the longest duplicate substring. The signature of the function is: 'string longestDuplicateSubstring(vector<string>& words)'.
a)
Use a Trie to insert all the words and find the longest duplicate substring using a depth-first search
b)
Use a Trie to insert all the words and find the longest duplicate substring using a breadth-first search
c)
Use a Trie to insert all the words and find the longest duplicate substring using dynamic programming
d)
Use a Trie to insert all the words and find the longest duplicate substring using the Boyer-Moore algorithm
Correct answer is option 'A'. Can you explain this answer?

Startup Central Classes answered

To find the longest duplicate substring in a list of words using a Trie, you can insert all the words into the Trie and then use a depth-first search to find the longest duplicate substring.

View Answers

You are given a Trie data structure and a word. Implement the 'remove' function that removes the word from the Trie. The signature of the function is: 'void remove(TrieNode* root, string word)'.
a)
Use recursion to traverse the Trie and remove the word from the Trie
b)
Use a stack to traverse the Trie and remove the word from the Trie
c)
Use a queue to traverse the Trie and remove the word from the Trie
d)
Use a hash table to store the Trie nodes and remove the word from the Trie
Correct answer is option 'A'. Can you explain this answer?

Neeraj Singh Kushwah answered

To implement the 'remove' function that removes a word from the Trie, you can use recursion to traverse the Trie and locate the nodes corresponding to the characters of the word. Once you reach the last character, you can remove the nodes in reverse order.

View Answers

In the Boggle game, what is the purpose of a TRIE data structure?
a)
To store the entire board configuration
b)
To store the dictionary of valid words
c)
To track the score of the player
d)
To determine the valid positions for placing letters on the board
Correct answer is option 'B'. Can you explain this answer?

Tom Tattle answered

The purpose of a TRIE data structure in the Boggle game is to store the dictionary of valid words. The TRIE allows for efficient word search and validation during the Boggle game.

View Answers

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;
}
a)
0
b)
1
c)
2
d)
Compiler Error
Correct answer is option 'A'. Can you explain this answer?

Diksha Sharma answered

The 'deleteWord' function is called to delete the word "hello" from the TRIE. After deletion, the 'countWords' function is called to count the number of words in the TRIE. Since "hello" was deleted, the output will be 0.

View Answers

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;
}
a)
1, 2, 0
b)
1, 1, 0
c)
0, 1, 0
d)
0, 2, 0
Correct answer is option 'C'. Can you explain this answer?

Coders Trust answered

The 'countPrefixes' function is called to count the number of prefixes in the TRIE. In this case, "apple," "banana," "cherry," and "cat" are inserted into the TRIE using the 'insert' function. The output will be 0 for "apx" because there is no word with that prefix in the TRIE, 1 for "ca" because "cat" has "ca" as a prefix, and 0 for "apx" because there is no word with that prefix in the TRIE.

View Answers

Which of the following is NOT a typical optimization technique used in the Boggle game using TRIE data structure?
a)
Memoization
b)
Backtracking
c)
Pruning
d)
Heuristic algorithms
Correct answer is option 'D'. Can you explain this answer?

Tom Tattle answered

Heuristic algorithms are not typically used as optimization techniques in the Boggle game using a TRIE data structure. Optimization techniques such as memoization, backtracking, and pruning can be applied to improve the performance of the Boggle game. Heuristic algorithms, on the other hand, are not directly related to the TRIE structure or the game itself.

View Answers

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;
}
a)
1
b)
2
c)
10
d)
Compiler Error
Correct answer is option 'B'. Can you explain this answer?

Diksha Sharma answered

The 'countWords' function counts the number of words in the TRIE. In this case, "hello" and "world" are inserted into the TRIE using the 'insert' function, so the output will be 2.

View Answers

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;
}
a)
apple (Weight: 40)
b)
apple (Weight: 40), banana (Weight: 47), cherry (Weight: 60), cat (Weight: 35)
c)
apple (Weight: 25), banana (Weight: 30), cherry (Weight: 35), cat (Weight: 40)
d)
banana (Weight: 7), cherry (Weight: 7), cat (Weight: 3)
Correct answer is option 'B'. Can you explain this answer?

Tech Era answered

The output of the code will be "True" because the 'deleteWord' function is called to delete the word "hello" from the TRIE. Since "hello" was successfully deleted, the 'search' function will return true.

View Answers

Given a list of strings, how can you efficiently build an auto-complete feature using a Trie?
a)
Insert all the strings into the Trie and use the search function to find matching prefixes
b)
Insert all the strings into a vector and use binary search to find matching prefixes
c)
Insert all the strings into a set and use the find function to find matching prefixes
d)
Insert all the strings into a priority queue and use the pop function to find matching prefixes
Correct answer is option 'A'. Can you explain this answer?

Diksha Sharma answered

To build an auto-complete feature using a Trie, you need to insert all the strings into the Trie. Then, when the user enters a partial string, you can use the search function to find matching prefixes and suggest possible completions.

View Answers

What will be the output of the following code?
#include <iostream>
#include "Trie.h"
int main() {
Trie trie;
trie.insert("apple");
trie.insert("banana");
trie.insert("cat");
std::cout << trie.countPrefixes("a") << std::endl;
std::cout << trie.countPrefixes("b") << std::endl;
std::cout << trie.countPrefixes("ca") << std::endl;
return 0;
}
a)
2 1 1
b)
1 1 2
c)
1 1 0
d)
0 0 0
Correct answer is option 'A'. Can you explain this answer?

Diksha Sharma answered

The output of the code will be:
The code creates a Trie and inserts the strings "apple", "banana", and "cat". It then counts the number of strings with the prefixes "a", "b", and "ca" using the 'countPrefixes' function. The function returns the count of strings with the given prefix.

View Answers

What will be the output of the following code?
#include <iostream>
#include "Trie.h"
int main() {
Trie trie;
trie.insert("apple");
trie.insert("banana");
trie.insert("cat");
std::cout << trie.search("apple") << std::endl;
std::cout << trie.search("dog") << std::endl;
std::cout << trie.search("cat") << std::endl;
return 0;
}
a)
1 0 1
b)
0 1 0
c)
1 1 1
d)
1 0 0
Correct answer is option 'A'. Can you explain this answer?

Ritesh Kumar Shivhare answered

The output of the code will be:
1
0
1
The code creates a Trie and inserts the strings "apple", "banana", and "cat". It then searches for the strings "apple", "dog", and "cat" using the 'search' function. The function returns 1 if the string is found in the Trie and 0 otherwise.

View Answers

What will be the output of the following code?
#include <iostream>
#include "Trie.h"
int main() {
Trie trie;
trie.insert("apple");
trie.insert("banana");
trie.insert("cat");
std::cout << trie.startsWith("a") << std::endl;
std::cout << trie.startsWith("b") << std::endl;
std::cout << trie.startsWith("d") << std::endl;
return 0;
}
a)
1 1 1
b)
1 1 0
c)
1 0 0
d)
0 0 0
Correct answer is option 'B'. Can you explain this answer?

Hackers World answered

The output of the code will be:
1
1
0
The code creates a Trie and inserts the strings "apple", "banana", and "cat". It then checks if the Trie contains strings starting with the characters "a", "b", and "d" using the startsWith function. The function returns 1 if there are strings 'starting with' the given prefix and 0 otherwise.

View Answers

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;
}
a)
True, True
b)
False, False
c)
True, False
d)
False, True
Correct answer is option 'C'. Can you explain this answer?

TeamUnknown answered

The output of the code will be "True" because the word "hello" is inserted into the TRIE using the 'insert' function, and the 'search' function returns true for the word "hello".

View Answers

Which of the following is NOT a step in the Boggle game using TRIE data structure?
a)
Traverse the board and check for all possible words starting at each cell
b)
Use a TRIE to store the dictionary of valid words
c)
Implement a recursive function to explore all possible paths on the board
d)
Store the frequency count of each word found in the TRIE
Correct answer is option 'D'. Can you explain this answer?

Coders Trust answered

Storing the frequency count of each word found in the TRIE is not a step in the Boggle game using TRIE data structure. The TRIE is primarily used for efficient word search and validation, but frequency counts are not directly related to the TRIE structure.

View Answers

Given a Trie data structure, how can you efficiently count the number of strings that have a given prefix? Implement the 'countPrefix' function that returns the count of strings with a given prefix. The signature of the function is: 'int countPrefix(TrieNode* root, string prefix)'.
a)
Use recursion to traverse the Trie and count the number of strings with the given prefix
b)
Use a stack to traverse the Trie and count the number of strings with the given prefix
c)
Use a queue to traverse the Trie and count the number of strings with the given prefix
d)
Use a hash table to store the Trie nodes and count the number of strings with the given prefix
Correct answer is option 'A'. Can you explain this answer?

Startup Central Classes answered

To count the number of strings with a given prefix in a Trie, you can use recursion to traverse the Trie until reaching the last character of the prefix. Then, you can count the number of strings below that point.

View Answers

You are given a Trie data structure and a word. Implement the 'search' function that returns 'true' if the word exists in the Trie and 'false' otherwise. The signature of the function is: 'bool search(TrieNode* root, string word)'.
a)
Use recursion to traverse the Trie and check if the word exists
b)
Use a stack to traverse the Trie and check if the word exists
c)
Use a queue to traverse the Trie and check if the word exists
d)
Use a hash table to store the Trie nodes and check if the word exists
Correct answer is option 'A'. Can you explain this answer?

Diksha Sharma answered

To implement the 'search' function that checks if a word exists in the Trie, you can use recursion to traverse the Trie and compare each character of the word with the corresponding nodes in the Trie.

View Answers

What will be the output of the following code?
#include <iostream>
#include "Trie.h"
int main() {
Trie trie;
trie.insert("apple");
trie.insert("banana");
trie.insert("cat");
trie.remove("apple");
std::cout << trie.search("apple") << std::endl;
std::cout << trie.search("banana") << std::endl;
return 0;
}
a)
1 1
b)
0 1
c)
1 0
d)
0 0
Correct answer is option 'B'. Can you explain this answer?

Hackers World answered

The output of the code will be:
0
1
The code creates a Trie and inserts the strings "apple", "banana", and "cat". It then removes the string "apple" from the Trie using the 'remove' function. After that, it 'searches' for the strings "apple" and "banana" using the search function. The function returns 1 if the string is found in the Trie and 0 otherwise.

View Answers

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;
}
a)
True, True, False
b)
False, False, True
c)
True, True, True
d)
False, True, False
Correct answer is option 'D'. Can you explain this answer?

TeamUnknown answered

The output of the code will be "False" for the first search because the word "bye" is not present in the TRIE. The output will be "True" for the second search because the word "world" is present in the TRIE. The output will be "False" for the third search because the word "bye" is not present in the TRIE.

View Answers

What is the time complexity of inserting a word into a TRIE with N nodes?
a)
O(1)
b)
O(log N)
c)
O(N)
d)
O(M), where M is the length of the word
Correct answer is option 'D'. Can you explain this answer?

Vikram Singh Baghel answered

The time complexity of inserting a word into a TRIE is O(M), where M is the length of the word. This is because we need to traverse the TRIE for each character in the word.

View Answers

Which of the following is NOT a disadvantage of using a TRIE?
a)
Requires more memory compared to other data structures
b)
Slower than hash tables for exact match lookups
c)
Difficulty in implementing compared to other data structures
d)
Inefficient for handling large datasets
Correct answer is option 'D'. Can you explain this answer?

TeamUnknown answered

TRIEs are efficient for handling large datasets, especially when it comes to searching for words or prefixes. They have a time complexity of O(M), where M is the length of the word being searched, which makes them suitable for large datasets.

View Answers

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;
}
a)
False
b)
True
c)
Compiler Error
d)
Undefined Behavior
Correct answer is option 'A'. Can you explain this answer?

TeamUnknown answered

The output of the code will be "False" because the 'deleteWord' function is called to delete the word "hello" from the TRIE, and then the 'search' function is called to check if the word "hello" is still present in the TRIE. Since it was deleted, the output will be "False".

View Answers

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;
}
a)
apple, banana, cherry, cat
b)
a, b, c
c)
app, ban, che, cat
d)
ap, ban, che, cat
Correct answer is option 'A'. Can you explain this answer?

Coders Trust answered

The 'printWords' function is called to print all the words in the TRIE. In this case, "apple," "banana," "cherry," and "cat" are inserted into the TRIE using the 'insert' function, so the output will be "apple, banana, cherry, cat".

View Answers

Which of the following problems can be efficiently solved using TRIE?
a)
Finding the shortest path in a weighted graph
b)
Counting the number of occurrences of words in a large text
c)
Sorting an array of integers in ascending order
d)
Finding the maximum sum subarray in an array
Correct answer is option 'B'. Can you explain this answer?

Tech Era answered

TRIEs can efficiently count the number of occurrences of words in a large text. By traversing the TRIE and keeping track of the count at each end-of-word node, we can quickly determine the frequency of each word.

View Answers

In a Trie, each node typically contains:
a)
A single character and a pointer to the parent node
b)
A single character and a pointer to the child node
c)
Multiple characters and a pointer to the parent node
d)
Multiple characters and a pointer to the child node
Correct answer is option 'D'. Can you explain this answer?

Ritesh Kumar Shivhare answered

In a Trie, each node typically contains multiple characters and a pointer to the child node. The child node represents the next character in the string.

View Answers

What will be the output of the following code?
#include <iostream>
#include "Trie.h"
int main() {
Trie trie;
trie.insert("apple");
trie.insert("banana");
trie.insert("cat");
std::cout << trie.longestPrefix("applesauce") << std::endl;
std::cout << trie.longestPrefix("carrot") << std::endl;
std::cout << trie.longestPrefix("catnip") << std::endl;
return 0;
}
a)
apple cat ""
b)
apple "" cat
c)
"" "" ""
d)
Error: longestPrefix() is not a valid function in Trie
Correct answer is option 'B'. Can you explain this answer?

Hackers World answered

The output of the code will be:
apple
""
cat
The code creates a Trie and inserts the strings "apple", "banana", and "cat". It then finds the longest prefix of the given strings using the 'longestPrefix' function. The function returns the longest prefix that exists in the Trie for each given string.

View Answers

Which of the following problems can be efficiently solved using Tries?
a)
Finding the shortest path in a weighted graph
b)
Checking whether two strings are anagrams
c)
Finding the median of a sorted array
d)
Calculating the factorial of a number
Correct answer is option 'B'. Can you explain this answer?

Ritesh Kumar Shivhare answered

Tries can be used to efficiently check whether two strings are anagrams. By inserting one string into a Trie and then searching for the other string, we can determine if they have the same characters in the same quantities.

View Answers

Which of the following is the correct definition of a Trie data structure?
a)
A tree-like data structure used to efficiently store and retrieve strings
b)
A graph-like data structure used to store integers
c)
An array-based data structure used to implement stacks
d)
A linked list-based data structure used to store characters
Correct answer is option 'A'. Can you explain this answer?

Ritesh Kumar Shivhare answered

Tries are tree-like data structures commonly used to store and retrieve strings. Each node represents a character, and the edges represent the next characters in the strings.

View Answers

Chapter doubts & questions for Tries - DSA in C++ 2024 is part of Software Development exam preparation. The chapters have been prepared according to the Software Development exam syllabus. The Chapter doubts & questions, notes, tests & MCQs are made for Software Development 2024 Exam. Find important definitions, questions, notes, meanings, examples, exercises, MCQs and online tests here.

Chapter doubts & questions of Tries - DSA in C++ in English & Hindi are available as part of Software Development exam. Download more important topics, notes, lectures and mock test series for Software Development Exam by signing up for free.