Tries (Prefix Trees) Quiz
40 comprehensive questions exploring trie data structures — with 16 code examples covering trie insertion, search operations, prefix queries, and memory optimization techniques in this cpp quiz.
40 Questions
~80 minutes
1
Question 1
What is a trie data structure?
A
A tree-based data structure where each node represents a character in a string, with paths from root to leaf representing complete words, enabling efficient prefix-based operations and string storage with shared common prefixes
B
A binary search tree for strings
C
A hash table for strings
D
A linked list of strings
2
Question 2
In a trie, what does each node typically contain?
text
Trie node: children array/map, endOfWord flag
Children indexed by characterA
An array or map of child nodes indexed by characters, and a boolean flag indicating whether the node represents the end of a complete word, allowing the trie to store multiple strings efficiently with shared prefixes
B
The complete string
C
Only the first character
D
Node values like in BST
3
Question 3
What is the time complexity of trie search?
A
O(m) where m is the length of the search string, as the search follows a single path from root to the target node, with each character access taking constant time in a properly implemented trie
B
O(log n)
C
O(1)
D
O(n)
4
Question 4
How does trie insertion work?
text
Insert word: traverse/create nodes for each char
Mark last node as endOfWordA
By traversing the trie character by character, creating new nodes for characters that don't exist, and marking the final node as the end of a word, allowing multiple words to share common prefixes efficiently
B
By inserting at the root only
C
By replacing existing nodes
D
By using binary search
5
Question 5
What is the advantage of tries over hash tables for string operations?
A
Tries support prefix-based operations and ordered traversal, while hash tables provide only exact matches, making tries superior for autocomplete and dictionary applications requiring prefix queries and alphabetical ordering
B
Tries are faster for exact matches
C
Tries use less memory
D
Hash tables support prefixes better
6
Question 6
How does trie prefix search work?
text
Prefix search: find node for prefix
Then traverse subtree for completionsA
By first locating the node corresponding to the prefix string, then traversing the subtree rooted at that node to collect all complete words that start with the given prefix, enabling efficient autocomplete functionality
B
By searching the entire trie
C
By using binary search
D
Prefix search is not supported
7
Question 7
What is the space complexity of a trie?
A
O(total characters) in the worst case when there are no shared prefixes, but often much better with common prefixes, as each character is stored only once regardless of how many words share that prefix
B
O(1)
C
O(log n)
D
O(n²)
8
Question 8
How is a trie typically implemented?
cpp
struct TrieNode {
TrieNode* children[26];
bool isEndOfWord;
};A
Using nodes with an array or map of child pointers indexed by characters, and a flag to mark word endings, providing O(1) access to children when using arrays for limited alphabets like English letters
B
Using a single array
C
Using a hash table only
D
Using a linked list
9
Question 9
What is the worst-case time complexity for trie insertion?
A
O(m) where m is the length of the string being inserted, as each character requires traversing or creating a single node, with the operation following a single path from root to the insertion point
B
O(n)
C
O(log n)
D
O(1)
10
Question 10
In trie applications, what is autocomplete functionality?
text
Autocomplete: find prefix node
DFS/BFS subtree for word completionsA
Finding all words in the trie that start with a given prefix by locating the prefix node and then traversing the subtree to collect complete words, providing efficient suggestions for partial string inputs
B
Finding exact matches only
C
Finding the longest word
D
Autocomplete is not possible with tries
11
Question 11
What is the trie property that enables prefix operations?
A
The hierarchical structure where common prefixes are shared in a single path, allowing prefix nodes to serve as roots for all words sharing that prefix, enabling efficient subtree traversals for prefix-based queries
B
All words are stored separately
C
The trie is balanced
D
No prefix sharing occurs
12
Question 12
How does trie handle case sensitivity?
text
Case sensitive: 'A' != 'a' different children
Case insensitive: normalize to lower/upperA
By default tries are case-sensitive with different children for 'A' and 'a', but case-insensitive behavior can be implemented by normalizing all characters to lowercase or uppercase before insertion and search operations
B
Tries ignore case always
C
Tries convert everything to uppercase
D
Case sensitivity cannot be handled
13
Question 13
What is the memory issue with standard trie implementations?
A
Sparse arrays waste memory when the alphabet is large but many characters are unused, as each node allocates space for all possible children even when most pointers remain null, leading to significant memory overhead
B
Tries use too little memory
C
Memory usage is always optimal
D
No memory issues exist
14
Question 14
How can tries be memory-optimized?
text
Use map instead of array: only store used children
Compress chains of single-child nodesA
By using dynamic maps instead of fixed arrays for children, storing only used characters, and implementing compression techniques like path compression to merge chains of nodes with single children into single edges
B
By using larger arrays
C
By storing complete strings
D
Memory optimization is not possible
15
Question 15
What is the significance of the endOfWord flag in tries?
A
It distinguishes between prefix nodes and complete word nodes, allowing words like 'car' and 'card' to coexist where 'car' is marked as a word but 'card' continues with additional characters from that node
B
It stores the word length
C
It indicates node color
D
The flag is not needed
16
Question 16
How does trie support dictionary operations?
cpp
Dictionary: insert all words
Search: traverse and check endOfWord
Prefix: find node, count subtree wordsA
By storing words during insertion with endOfWord markers, enabling exact searches by traversing to the target node and checking the flag, and supporting prefix queries by counting marked nodes in relevant subtrees
B
By storing words in sorted order
C
By using hash functions
D
Dictionary operations are not supported
17
Question 17
What is the advantage of tries in IP routing?
A
Tries enable longest prefix matching for IP address lookups, where routing tables can be organized as tries with IP prefixes as paths, allowing efficient determination of the best matching route for packet forwarding
B
Tries are faster than hash tables
C
Tries use less memory for IPs
D
IP routing doesn't use tries
18
Question 18
How does trie handle deletion operations?
text
Delete: find word, unset endOfWord
Remove nodes if no children and not endOfWordA
By locating the word's final node and unmarking it as endOfWord, then removing nodes upwards if they have no children and are not marked as word endings, preventing unnecessary node retention
B
By removing the entire path
C
By marking nodes as deleted
D
Deletion is not supported in tries
19
Question 19
What is the cache performance of trie operations?
A
Generally poor due to pointer chasing through multiple nodes for each operation, as trie traversals follow chains of pointers that may not be contiguous in memory, leading to cache misses during character-by-character navigation
B
Excellent due to contiguous storage
C
Same as arrays
D
Cache performance is irrelevant for tries
20
Question 20
In trie applications, what is spell checking?
text
Spell check: search word in trie
If not found, suggest similar wordsA
Verifying word existence by searching the trie, and when words are not found, using trie structure to suggest corrections by finding words with similar prefixes or minimal edit distances within the stored vocabulary
B
Checking word length only
C
Using phonetic algorithms
D
Spell checking is not possible with tries
21
Question 21
What is the trie structure advantage over binary search trees for strings?
A
Tries provide O(m) search time independent of the number of stored strings, while BSTs require O(m log n) time, making tries superior for large dictionaries with frequent lookups of varying string lengths
B
Tries are easier to implement
C
Tries use less memory
D
BSTs are better for strings
22
Question 22
How does trie support counting words with a prefix?
text
Prefix count: find prefix node
Count endOfWord flags in subtreeA
By locating the node for the prefix and then traversing the subtree to count all nodes marked as endOfWord, providing an efficient way to determine how many words share a common prefix in the dictionary
B
By counting all nodes
C
By using separate counters
D
Prefix counting is not supported
23
Question 23
What is the issue with large alphabets in tries?
A
Large alphabets like Unicode create sparse children arrays with mostly null pointers, wasting significant memory, which can be mitigated by using dynamic maps or hash tables instead of fixed-size arrays for character indexing
B
Large alphabets make tries faster
C
Large alphabets reduce memory usage
D
No issues with large alphabets
24
Question 24
How does trie enable lexicographical ordering?
text
Lex order: inorder traversal of trie
Visit children in character orderA
Through level-order or DFS traversal that visits children in character order, naturally producing strings in sorted lexicographical order since the trie structure mirrors the alphabetical hierarchy of the stored strings
B
By storing words in sorted arrays
C
By using comparison functions
D
Lex ordering is not supported
25
Question 25
What is path compression in tries?
A
A memory optimization technique that merges chains of nodes with single children into single edges storing the compressed string segment, reducing the number of nodes while maintaining the same functionality for search operations
B
Compressing the root node
C
Removing all paths
D
Path compression doesn't exist
26
Question 26
In trie applications, what is the significance of the root node?
text
Root: empty string, start of all words
No character stored at rootA
The root represents the empty string and serves as the starting point for all words in the trie, containing children for the first characters of all stored strings but storing no character itself in standard implementations
B
It stores the longest word
C
It stores all words
D
The root is not significant
27
Question 27
How does trie support wildcard searches?
A
By traversing the trie with pattern matching where wildcard characters like '.' can match any character by trying all possible children at that position, enabling flexible pattern searches within the trie structure
B
By using regular expressions
C
By converting to hash tables
D
Wildcard searches are not supported
28
Question 28
What is the practical memory usage of tries vs hash sets for strings?
text
Trie: O(total chars) shared prefixes
Hash set: O(total chars) no sharingA
Tries often use less memory than hash sets for strings with common prefixes due to shared character nodes, while hash sets store each string completely separately, making tries more memory-efficient for natural language dictionaries
B
Hash sets always use less memory
C
Tries always use less memory
D
Memory usage is identical
29
Question 29
How does trie handle non-English alphabets?
A
By using appropriate character encoding and indexing schemes, such as UTF-8 with dynamic maps for Unicode characters or custom indexing for specific alphabets, allowing tries to work with any character set beyond just ASCII
B
By converting to English
C
By using only ASCII characters
D
Non-English alphabets are not supported
30
Question 30
What is the trie advantage in mobile text input?
text
Mobile: prefix matching for suggestions
T9-style predictive textA
Tries enable fast prefix-based word completion for virtual keyboards, where partial inputs can quickly find candidate words by traversing the trie structure, supporting features like autocorrect and predictive text input efficiently
B
Tries make typing faster
C
Tries reduce battery usage
D
Mobile input doesn't use tries
31
Question 31
What is the significance of tries in algorithm design?
A
Tries provide efficient solutions for string processing problems requiring prefix operations, autocomplete, and dictionary lookups, offering better asymptotic performance than alternatives for applications dealing with large sets of strings
B
They are the fastest data structure
C
They use the least memory
D
They are easiest to implement
32
Question 32
How does trie compare to ternary search trees?
text
Trie: one child per char
TST: three children (left, mid, right)A
Tries use one child per character for simpler implementation and better cache performance in some cases, while ternary search trees use three children per node for more compact representation with fewer nodes but more complex balancing
B
Tries are always better
C
Ternary trees are always better
D
They are identical
33
Question 33
What is the trie limitation for very long strings?
A
Long strings create deep trie structures with many nodes, potentially causing stack overflow in recursive implementations and increasing memory usage linearly with string length, though this can be mitigated with iterative approaches
B
Long strings make tries faster
C
Long strings reduce memory usage
D
No limitations for long strings
34
Question 34
How does trie support longest common prefix operations?
text
LCP: traverse until paths diverge
Count matching charactersA
By simultaneously traversing paths for multiple strings from the root until the paths diverge, counting the number of matching characters along the common path to find the longest prefix shared by all strings efficiently
B
By comparing strings directly
C
By using binary search
D
LCP operations are not supported
35
Question 35
What is the cache-friendly optimization for tries?
A
Using contiguous arrays for children instead of pointers, or implementing burst tries that convert pointer-based nodes to arrays when subtrees become dense, improving cache locality and reducing pointer chasing overhead
B
Using more pointers
C
Using recursive implementations
D
Cache optimization is not possible
36
Question 36
In trie applications, what is the significance of endOfWord flags?
text
endOfWord: allows multiple words per path
'car' and 'card' both validA
EndOfWord flags allow the trie to store words of different lengths that share common prefixes, enabling efficient storage of related words like 'car' and 'card' where both can be valid words from the same node path
B
They store word frequencies
C
They indicate node depth
D
The flags are optional
37
Question 37
How does trie handle reverse lookups?
A
Reverse tries can be implemented by storing strings in reverse order, enabling suffix-based searches and reverse lookups for applications like finding words ending with specific patterns or reverse domain name resolution
B
By reversing the trie structure
C
By using separate data structures
D
Reverse lookups are not supported
38
Question 38
What is the practical implementation choice for trie children?
cpp
Small alphabet: array[26]
Large alphabet: unordered_map<char, Node*>A
Arrays for small alphabets like English (26 letters) providing O(1) access, and dynamic maps or hash tables for large character sets like Unicode, balancing between memory efficiency and access speed based on the character domain
B
Always use arrays
C
Always use maps
D
Implementation choice doesn't matter
39
Question 39
How does trie support approximate string matching?
A
By allowing limited mismatches during traversal where a small number of character differences are tolerated, or by using multiple tries for different edit distances, enabling fuzzy matching and spell correction capabilities
B
By using edit distance algorithms
C
By storing all possible variations
D
Approximate matching is not supported
40
Question 40
Considering trie data structures and their applications in string processing, which fundamental property makes tries essential for efficient prefix-based operations despite potential memory overhead?
A
The shared prefix structure enables O(m) time complexity for search and insertion operations independent of the number of stored strings, while supporting prefix queries and ordered traversal that are impossible or inefficient with hash-based approaches
B
Guaranteed O(1) performance
C
Minimal memory requirements
D
Simplicity of implementation only