Autocomplete System with Trie in DSA C - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is a Trie in the context of an autocomplete system?

A Trie is a tree-like data structure that stores words by sharing common prefixes. It helps quickly find all words that start with a given prefix, making it ideal for autocomplete.

intermediate

How does a Trie improve autocomplete search speed compared to searching a list of words?

A Trie allows searching by prefix in time proportional to the prefix length, not the number of words. This means autocomplete suggestions can be found faster than scanning all words.

beginner

In a Trie node, what does each child represent?

Each child represents a possible next character in words that share the current prefix. For example, if the prefix is 'ca', children might be nodes for 't', 'r', or 'n' to form words like 'cat', 'car', or 'can'.

beginner

What is the purpose of a boolean flag in a Trie node?

The boolean flag marks if the path from the root to this node forms a complete word. This helps distinguish prefixes from actual words in the Trie.

intermediate

Describe the steps to find autocomplete suggestions using a Trie.

1. Traverse the Trie following the prefix characters.
2. Once at the prefix node, perform a depth-first search to collect all complete words below.
3. Return these words as autocomplete suggestions.

What does each node in a Trie typically store?

A A character, children nodes, and a boolean flag for word end

B Only a character

C A list of all words starting with that prefix

D The full word

Each Trie node stores a character, pointers to children nodes for next characters, and a boolean flag indicating if it ends a word.

Why is a Trie efficient for autocomplete?

A It allows prefix search in time proportional to prefix length

B It stores words in alphabetical order

C It uses less memory than arrays

D It sorts words automatically

Trie allows searching all words with a given prefix quickly by following nodes for each prefix character.

What happens if a prefix is not found in the Trie during autocomplete?

A Return the longest word in the Trie

B Return all words in the Trie

C Return the root node's children

D Return an empty list of suggestions

If the prefix path does not exist, no words start with that prefix, so autocomplete returns no suggestions.

Which traversal method is commonly used to collect autocomplete suggestions from a Trie node?

A Breadth-first search

B In-order traversal

C Depth-first search

D Level-order traversal

Depth-first search explores all paths from the prefix node to find complete words for suggestions.

What is the time complexity to insert a word of length n into a Trie?

A O(1)

B O(n)

C O(log n)

D O(n^2)

Insertion requires creating or traversing nodes for each character, so time is proportional to word length n.

Explain how a Trie supports autocomplete functionality step-by-step.

Think about how you find words starting with the same letters quickly.

Describe the structure of a Trie node and its role in storing words.

Imagine each node as a letter in a word path.

Practice

1. What is the main purpose of using a Trie in an autocomplete system?

easy

A. To store words in a tree structure for fast prefix search

B. To sort words alphabetically before searching

C. To store words in a linked list for sequential access

D. To compress words into a hash table for quick lookup

Solution

1. Step 1: Understand the role of Trie in autocomplete

   A Trie stores words character by character in a tree, allowing quick prefix matching.

2. Step 2: Compare with other data structures

   Linked lists and hash tables do not efficiently support prefix searches like Tries do.

3. Final Answer:

   To store words in a tree structure for fast prefix search -> Option A

4. Quick Check:

   Trie = fast prefix search [OK]

Hint: Trie = tree for prefixes, perfect for autocomplete [OK]

Common Mistakes:

• Confusing Trie with hash table
• Thinking linked list is efficient for prefix search
• Assuming sorting alone solves autocomplete

2. Which of the following is the correct way to declare a Trie node structure in C for lowercase English letters?

easy

A. typedef struct TrieNode { struct TrieNode* children[26]; int isEndOfWord; } TrieNode;

B. typedef struct TrieNode { struct TrieNode* children[52]; int isEndOfWord; } TrieNode;

C. typedef struct TrieNode { struct TrieNode* children[10]; int isEndOfWord; } TrieNode;

D. typedef struct TrieNode { struct TrieNode* children; int isEndOfWord; } TrieNode;

Solution

1. Step 1: Identify the size of children array for lowercase letters

   There are 26 lowercase English letters, so children array size should be 26.

2. Step 2: Check the structure correctness

   Each node has an array of pointers to children and a flag for end of word.

3. Final Answer:

   typedef struct TrieNode { struct TrieNode* children[26]; int isEndOfWord; } TrieNode; -> Option A

4. Quick Check:

   26 children for lowercase letters [OK]

Hint: 26 children pointers for lowercase English letters [OK]

Common Mistakes:

• Using 52 for uppercase + lowercase without clarification
• Using 10 for digits only
• Not using array for children pointers

3. Given the following code snippet inserting words into a Trie and searching for prefix "app":

insert("apple");
insert("app");
insert("application");
searchPrefix("app");

What will searchPrefix("app") return?

medium

A. ["app"]

B. ["app", "apple", "application"]

C. ["apple", "application"]

D. []

Solution

1. Step 1: Understand insertion of words

   Words "apple", "app", and "application" are inserted, all sharing prefix "app".

2. Step 2: Search prefix "app" returns all words starting with "app"

   So, it returns all three words: "app", "apple", and "application".

3. Final Answer:

   ["app", "apple", "application"] -> Option B

4. Quick Check:

   Prefix "app" matches 3 words [OK]

Hint: Prefix search returns all words starting with prefix [OK]

Common Mistakes:

• Returning only exact matches
• Missing shorter word "app"
• Returning empty list incorrectly

4. Consider this buggy C code snippet for inserting a word into a Trie:

void insert(TrieNode* root, const char* word) {
  TrieNode* node = root;
  for (int i = 0; word[i] != '\0'; i++) {
    int index = word[i] - 'a';
    if (node->children[index] == NULL) {
      node->children[index] = malloc(sizeof(TrieNode));
      memset(node->children[index], 0, sizeof(TrieNode));
    }
    node = node->children[index];
  }
  node->isEndOfWord = 1;
}

What is the main bug in this code?

medium

A. Root node is not checked for NULL

B. Index calculation is incorrect

C. isEndOfWord is set before loop

D. New nodes are not initialized after malloc

Solution

1. Step 1: Analyze malloc usage for new nodes

   malloc allocates memory but does not initialize children pointers or isEndOfWord flag.

2. Step 2: Consequence of missing initialization

   Uninitialized children pointers may cause undefined behavior during traversal or insertion.

3. Final Answer:

   New nodes are not initialized after malloc -> Option D

4. Quick Check:

   malloc needs initialization [OK]

Hint: Always initialize new Trie nodes after malloc [OK]

Common Mistakes:

• Assuming malloc zeroes memory
• Thinking index calculation is wrong
• Ignoring initialization of isEndOfWord

5. You want to extend a Trie-based autocomplete system to support case-insensitive search for English letters (both uppercase and lowercase). Which modification is the best approach?

hard

A. Store words as-is and compare characters ignoring case during search only

B. Increase children array size to 52 to store uppercase and lowercase separately

C. Convert all input words to lowercase before insertion and search, keep children array size 26

D. Use a hash map instead of array for children to store any character

Solution

1. Step 1: Consider memory and complexity

   Using 52 children doubles memory; hash map adds overhead; ignoring case only during search is inefficient.

2. Step 2: Normalize input for simplicity

   Converting all words to lowercase before insertion and search simplifies Trie structure and ensures consistent matching.

3. Final Answer:

   Convert all input words to lowercase before insertion and search, keep children array size 26 -> Option C

4. Quick Check:

   Normalize case before Trie operations [OK]

Hint: Normalize case before insert/search for simpler Trie [OK]

Common Mistakes:

• Doubling children array size unnecessarily
• Ignoring case only during search causes mismatch
• Using hash map adds complexity and overhead