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

Practice - 5 Tasks

1fill in blank

easy

Complete the code to create a new Trie node.

DSA Go

type TrieNode struct {
    children [26]*TrieNode
    isEnd bool
}

func NewTrieNode() *TrieNode {
    return &TrieNode{
        children: [26]*TrieNode{},
        isEnd: [1],
    }
}

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

Atrue

Bnil

Cfalse

D0

Attempts:

3 left

💡 Hint

Common Mistakes

Setting isEnd to true initially, which incorrectly marks the node as end of a word.

When creating a new Trie node, the isEnd flag should be false initially because no word ends at this node yet.

2fill in blank

medium

Complete the code to insert a word into the Trie.

DSA Go

func (t *TrieNode) Insert(word string) {
    node := t
    for _, ch := range word {
        index := ch - 'a'
        if node.children[index] == nil {
            node.children[index] = NewTrieNode()
        }
        node = node.children[[1]]
    }
    node.isEnd = true
}

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

Ach

Bindex

Cnode

Dword

Attempts:

3 left

💡 Hint

Common Mistakes

Using the character directly instead of the index to access children.

Using the word or node variable incorrectly.

We use the calculated index to move to the correct child node for the current character.

3fill in blank

hard

Fix the error in the DFS function to find the longest word.

DSA Go

func dfs(node *TrieNode, path string, result *string) {
    if !node.isEnd && len(path) > 0 {
        return
    }
    if len(path) > len(*result) || (len(path) == len(*result) && path < *result) {
        *result = path
    }
    for i := 0; i < 26; i++ {
        if node.children[i] != nil {
            dfs(node.children[i], path+string('a'+[1]), result)
        }
    }
}

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

Aresult

Bnode

Cpath

Di

Attempts:

3 left

💡 Hint

Common Mistakes

Using node or path instead of the loop index i to calculate the character.

Appending wrong characters causing incorrect word formation.

We add the character corresponding to index i to the path during DFS traversal.

4fill in blank

hard

Fill both blanks to complete the function that finds the longest word in the dictionary using Trie.

DSA Go

func longestWord(words []string) string {
    root := NewTrieNode()
    for _, word := range words {
        root.[1](word)
    }
    result := ""
    dfs(root, "", &result)
    return [2]
}

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

AInsert

BSearch

Cresult

Dwords

Attempts:

3 left

💡 Hint

Common Mistakes

Using Search instead of Insert to add words.

Returning the wrong variable.

We insert each word into the Trie, then return the result found by DFS.

5fill in blank

hard

Fill all three blanks to complete the DFS helper function that builds the longest word.

DSA Go

func dfs(node *TrieNode, path string, result *string) {
    if !node.isEnd && len(path) > 0 {
        return
    }
    if len(path) > len(*result) || (len(path) == len(*result) && path < *result) {
        *result = path
    }
    for [1] := 0; [2] < 26; [3]++ {
        if node.children[[1]] != nil {
            dfs(node.children[[1]], path+string('a'+[1]), result)
        }
    }
}

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

Ai

Bj

Ck

Dindex

Attempts:

3 left

💡 Hint

Common Mistakes

Using different variable names in loop parts causing syntax errors.

The loop variable i is used consistently for initialization, condition, and increment.

Practice

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

easy

A. To reverse the words quickly

B. To sort words alphabetically

C. To count the total number of words

D. To efficiently store and search words by their prefixes

Solution

1. Step 1: Understand Trie usage

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

2. Step 2: Connect Trie to longest word search

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

3. Final Answer:

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

4. Quick Check:

   Trie = prefix search [OK]

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

Common Mistakes:

• Confusing Trie with sorting algorithms
• Thinking Trie reverses words
• Assuming Trie counts words only

2. Which of the following Go code snippets correctly initializes a Trie node struct for storing children nodes?

easy

A. type TrieNode struct { children map[int]string; isWord string }

B. type TrieNode struct { children []int; isWord int }

C. type TrieNode struct { children map[rune]*TrieNode; isWord bool }

D. type TrieNode struct { children []string; isWord bool }

Solution

1. Step 1: Identify correct children type

   Children should map characters (rune) to TrieNode pointers for branching.

2. Step 2: Check isWord type

   isWord is a boolean indicating if node ends a valid word.

3. Final Answer:

   type TrieNode struct { children map[rune]*TrieNode; isWord bool } -> Option C

4. Quick Check:

   Children map[rune]*TrieNode and bool isWord [OK]

Hint: Children map uses rune keys and TrieNode pointers [OK]

Common Mistakes:

• Using slices instead of maps for children
• Wrong data types for children or isWord
• Using int or string instead of rune keys

3. Given the following Go code snippet that inserts words into a Trie and finds the longest word, what will be printed?

words := []string{"a", "app", "apple", "apply", "ap"}
trie := NewTrie()
for _, w := range words {
    trie.Insert(w)
}
result := trie.LongestWord()
fmt.Println(result)

medium

A. "app"

B. "apply"

C. "a"

D. "apple"

Solution

1. Step 1: Insert words into Trie

   All words "a", "ap", "app", "apple", "apply" are inserted.

2. Step 2: Find longest word built from prefixes

   "app" has all prefixes "a", "ap", "app" present as words. "apple" and "apply" lack "appl" prefix.

3. Final Answer:

   "app" -> Option A

4. Quick Check:

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

Hint: Longest word with all prefixes present wins, lex order breaks ties [OK]

Common Mistakes:

• Choosing "apple" or "apply" ignoring missing "appl"
• Picking lexicographically later word
• Not inserting all words before search

4. In the following Go code for inserting words into a Trie, what is the bug that prevents correct longest word detection?

func (t *Trie) Insert(word string) {
    node := t.root
    for _, ch := range word {
        if node.children[ch] == nil {
            node.children[ch] = &TrieNode{}
        }
        node = node.children[ch]
    }
    node.isWord = false
}

medium

A. isWord should be set to true, not false

B. children map is not initialized

C. Loop variable ch should be int, not rune

D. Function should return a value

Solution

1. Step 1: Check isWord assignment

   isWord marks end of a valid word and must be true, not false.

2. Step 2: Understand impact on longest word search

   Setting isWord false means no word end is recognized, breaking longest word logic.

3. Final Answer:

   isWord should be set to true, not false -> Option A

4. Quick Check:

   isWord = true marks word end [OK]

Hint: Set isWord true at word end to mark valid words [OK]

Common Mistakes:

• Setting isWord false instead of true
• Not initializing children map before use
• Ignoring rune type for characters

5. You have a list of words: ["w", "wo", "wor", "worl", "world", "banana", "ban", "bana", "banan"]. Using a Trie, which word will be the longest word in the dictionary where every prefix is also a word? Assume ties are broken by lexicographical order.

hard

A. "worl"

B. "world"

C. "banana"

D. "banan"

Solution

1. Step 1: Check prefixes for each candidate

   "world" has prefixes "w", "wo", "wor", "worl" all present.

2. Step 2: Check "banana" and its prefixes

   "banana" lacks prefixes like "b", "ba", so it fails.

3. Step 3: Compare longest valid words

   "world" (length 5) is longest with all prefixes present; "banana" (6) invalid, "banan" also invalid.

4. Final Answer:

   "world" -> Option B

5. Quick Check:

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

Hint: Check all prefixes exist; longest with lex order wins [OK]

Common Mistakes:

• Ignoring missing prefixes for banana
• Choosing shorter words
• Not applying lexicographical tie-break