Longest Word in Dictionary Using Trie in DSA Go - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Longest Word Search in Trie

What is the output of the following Go code that builds a Trie from a list of words and finds the longest word where all prefixes are also words in the list?

DSA Go

package main

import "fmt"

// TrieNode represents a node in the Trie
type TrieNode struct {
    children map[rune]*TrieNode
    isWord   bool
}

// Trie structure
type Trie struct {
    root *TrieNode
}

// Insert inserts a word into the Trie
func (t *Trie) Insert(word string) {
    node := t.root
    for _, ch := range word {
        if node.children[ch] == nil {
            node.children[ch] = &TrieNode{children: make(map[rune]*TrieNode)}
        }
        node = node.children[ch]
    }
    node.isWord = true
}

// LongestWord finds the longest word with all prefixes present
func (t *Trie) LongestWord() string {
    var result string
    var dfs func(node *TrieNode, path []rune)
    dfs = func(node *TrieNode, path []rune) {
        if len(path) > len(result) || (len(path) == len(result) && string(path) < result) {
            result = string(path)
        }
        for ch := range node.children {
            child := node.children[ch]
            if child.isWord {
                dfs(child, append(path, ch))
            }
        }
    }
    dfs(t.root, []rune{})
    return result
}

func main() {
    words := []string{"a", "app", "ap", "apply", "apple", "appl"}
    trie := &Trie{root: &TrieNode{children: make(map[rune]*TrieNode)}}
    for _, w := range words {
        trie.Insert(w)
    }
    fmt.Println(trie.LongestWord())
}

A "apply"

B "app"

C "apple"

D "appl"

💡 Hint

Check which words have all their prefixes also present in the list.

The code builds a Trie and searches for the longest word where every prefix is also a word in the list. Among the words, "apple" and "apply" are longest. Both "apple" and "apply" have all prefixes present, but lex order chooses "apple".

🧠 Conceptual

intermediate

Understanding Trie Node Structure

Which of the following best describes the purpose of the 'isWord' boolean in a Trie node when finding the longest word in a dictionary?

A It indicates if the node has any children nodes.

B It counts how many words pass through this node.

C It stores the character value of the node.

D It marks whether the node represents the end of a valid word in the dictionary.

💡 Hint

Think about how to know if a prefix is a complete word.

The 'isWord' boolean marks if the path to this node forms a complete word in the dictionary. This is crucial to check if all prefixes exist when searching for the longest word.

🔧 Debug

advanced

Identify the Bug in Trie Longest Word Search

What error will occur if the DFS function in the Trie LongestWord method does not check if child.isWord before recursing?

DSA Go

func (t *Trie) LongestWord() string {
    var result string
    var dfs func(node *TrieNode, path []rune)
    dfs = func(node *TrieNode, path []rune) {
        if len(path) > len(result) || (len(path) == len(result) && string(path) < result) {
            result = string(path)
        }
        for ch := range node.children {
            child := node.children[ch]
            // Missing check: if child.isWord
            dfs(child, append(path, ch))
        }
    }
    dfs(t.root, []rune{})
    return result
}

A The DFS will never terminate, causing infinite recursion.

B The function will include incomplete prefixes, resulting in incorrect longest word output.

C The code will produce a compilation error due to missing isWord check.

D The code will cause a runtime panic due to nil pointer dereference.

💡 Hint

Consider what happens if prefixes are not validated as words.

Without checking if child.isWord, the DFS explores nodes that do not represent complete words, so the result may include words whose prefixes are not valid words, violating the problem's condition.

🚀 Application

advanced

Longest Word Result After Insertions

Given the words inserted into the Trie: ["w", "wo", "wor", "worl", "world", "word", "war"], what will be the longest word returned by the LongestWord method?

A "world"

B "word"

C "war"

D "worl"

💡 Hint

Check which words have all prefixes present and are longest.

"world" has all prefixes "w", "wo", "wor", "worl" present as words. "word" also has prefixes but is shorter. "war" is shorter and "worl" is prefix but not longest.

🧠 Conceptual

expert

Lexicographical Order in Longest Word Selection

Why does the LongestWord method compare strings lexicographically when lengths are equal during DFS?

A To ensure the lexicographically smallest word is chosen among words of the same length.

B To speed up the DFS traversal by pruning branches early.

C To avoid visiting nodes that do not form valid words.

D To count the total number of words stored in the Trie.

💡 Hint

Think about tie-breaking when multiple words have the same length.

When multiple words have the same length, the problem requires choosing the lexicographically smallest one. Comparing strings lex order ensures this.

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