Longest Word in Dictionary Using Trie in DSA Python - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to insert a word into the Trie.

DSA Python

def insert_word(root, word):
    node = root
    for char in word:
        if char not in node.children:
            node.children[[1]] = TrieNode()
        node = node.children[char]
    node.is_end = True

Drag options to blanks, or click blank then click option'

Anode

Bword

Croot

Dchar

Attempts:

3 left

💡 Hint

Common Mistakes

Using the whole word as a key instead of the current character.

Using the root or node variable incorrectly.

We use the current character 'char' as the key to insert into the children dictionary.

2fill in blank

medium

Complete the code to check if a node marks the end of a word.

DSA Python

def is_word_end(node):
    return node.[1]

Drag options to blanks, or click blank then click option'

Ais_end

Bchildren

Cword

Droot

Attempts:

3 left

💡 Hint

Common Mistakes

Checking 'children' instead of 'is_end'.

Using undefined attributes.

The 'is_end' attribute tells if the node marks the end of a word.

3fill in blank

hard

Fix the error in the code that finds the longest word in the Trie.

DSA Python

def longest_word(root):
    result = ""
    def dfs(node, path):
        nonlocal result
        if not node.is_end and node != root:
            return
        if len(path) > len(result) or (len(path) == len(result) and path < result):
            result = path
        for char in sorted(node.children.keys()):
            dfs(node.children[[1]], path + char)
    dfs(root, "")
    return result

Drag options to blanks, or click blank then click option'

Anode

Bpath

Cchar

Dresult

Attempts:

3 left

💡 Hint

Common Mistakes

Using 'path' or 'node' instead of 'char' as key.

Accessing children with wrong variable.

We must use 'char' to access the child node in the children dictionary.

4fill in blank

hard

Fill both blanks to create a dictionary comprehension that maps words to their lengths for words longer than 3 characters.

DSA Python

words = ["apple", "bat", "cat", "applesauce"]
lengths = { [1]: [2] for word in words if len(word) > 3 }

Drag options to blanks, or click blank then click option'

Aword

Blen(word)

Cword.upper()

Dlen

Attempts:

3 left

💡 Hint

Common Mistakes

Using 'len' as key instead of word.

Using 'word.upper()' which changes the key.

The dictionary keys are words and values are their lengths.

5fill in blank

hard

Fill all three blanks to create a dictionary comprehension that maps uppercase words to their lengths for words longer than 3 characters.

DSA Python

words = ["apple", "bat", "cat", "applesauce"]
result = { [1]: [2] for word in words if len(word) [3] 3 }

Drag options to blanks, or click blank then click option'

Aword.upper()

Blen(word)

C>

D<

Attempts:

3 left

💡 Hint

Common Mistakes

Using '<' instead of '>' in the condition.

Using 'word' instead of 'word.upper()' as key.

Keys are uppercase words, values are lengths, and condition checks length greater than 3.

Practice

1. What is the main purpose of using a Trie data structure when finding the longest word in a dictionary?

easy

A. To efficiently store and search words by their prefixes

B. To sort words alphabetically

C. To count the total number of words

D. To reverse the words in the dictionary

Solution

1. Step 1: Understand Trie usage

   A Trie stores words by breaking them into characters and linking nodes for prefixes.

2. Step 2: Relate Trie to longest word search

   This structure allows quick prefix checks, which helps find the longest word built from other words.

3. Final Answer:

   To efficiently store and search words by their prefixes -> Option A

4. Quick Check:

   Trie = prefix search [OK]

Hint: Trie is best for prefix-based word searches [OK]

Common Mistakes:

• Thinking Trie sorts words alphabetically
• Confusing Trie with simple lists
• Assuming Trie counts words only

2. Which of the following is the correct way to insert a word into a Trie node in Python?

easy

A. node.children[char] = TrieNode() if char not in node.children else node.children[char]

B. node.children.add(char)

C. node.children.append(char)

D. node.children[char] = char

Solution

1. Step 1: Understand Trie children structure

   Trie children are stored in a dictionary mapping characters to TrieNode objects.

2. Step 2: Correct insertion method

   We check if character exists; if not, create new TrieNode and assign it to children dictionary.

3. Final Answer:

   node.children[char] = TrieNode() if char not in node.children else node.children[char] -> Option A

4. Quick Check:

   Insert uses dictionary with TrieNode [OK]

Hint: Use dictionary keys for children, not list or set [OK]

Common Mistakes:

• Using add() or append() on dictionary
• Assigning character instead of TrieNode
• Not checking if child exists before insertion

3. Given the words: ["a", "app", "apple", "apply", "ap"], what is the longest word that can be built one character at a time using the Trie method?

medium

A. "apply"

B. "app"

C. "apple"

D. "ap"

Solution

1. Step 1: Check each word's prefixes

   Words must have all prefixes present: "a", "ap", "app" are present; "apple" and "apply" require "appl" which is missing.

2. Step 2: Identify longest valid word

   "app" is the longest word where all prefixes exist in the list.

3. Final Answer:

   "app" -> Option B

4. Quick Check:

   Longest word with all prefixes = "app" [OK]

Hint: Check all prefixes exist before choosing longest word [OK]

Common Mistakes:

• Assuming "apple" or "apply" are valid without "appl"
• Ignoring prefix requirement
• Choosing shortest word instead

4. What is the error in this Trie insertion code snippet for building the longest word?

for word in words:
    node = root
    for char in word:
        if char not in node.children:
            node.children[char] = TrieNode
        node = node.children[char]
    node.is_word = True

medium

A. The root node should be reset after each character

B. The loop should iterate over characters in reverse

C. node.is_word should be set before the inner loop

D. TrieNode should be called with parentheses to create an instance

Solution

1. Step 1: Identify object creation mistake

   TrieNode is a class; to create an object, parentheses () are needed.

2. Step 2: Understand impact of missing parentheses

   Without (), node.children[char] stores the class itself, not an instance, causing errors on further access.

3. Final Answer:

   TrieNode should be called with parentheses to create an instance -> Option D

4. Quick Check:

   Instantiate TrieNode with () [OK]

Hint: Always use () to create class instances in Python [OK]

Common Mistakes:

• Forgetting parentheses when creating objects
• Setting flags in wrong loop place
• Resetting root incorrectly inside loops

5. You have a list of words: ["w", "wo", "wor", "worl", "world", "banana", "ban", "bana", "banan"]. Using a Trie, which word will be returned as the longest word built one character at a time from other words in the list?

hard

A. "worl"

B. "banana"

C. "world"

D. "banan"

Solution

1. Step 1: Verify prefix chains for each candidate

   "world" prefixes: "w", "wo", "wor", "worl", "world" all exist; "banana" and "banan" missing prefixes like "b", "ba"; "worl" is shorter than "world".

2. Step 2: Choose longest word with all prefixes present

   "world" is longest with all prefixes present in the list.

3. Final Answer:

   "world" -> Option C

4. Quick Check:

   Longest word with full prefix chain = "world" [OK]

Hint: Check full prefix chain exists before longest word [OK]

Common Mistakes:

• Choosing "banana" without full prefix chain
• Ignoring prefix requirement for "banan"
• Picking shorter word "worl" over "world"