Count Words with Given Prefix in DSA Go - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of prefix count after adding words

What is the output of the Go program that counts how many words start with the prefix "app" after adding the words "apple", "app", "application", "banana"?

DSA Go

package main

import (
	"fmt"
)

type TrieNode struct {
	children map[rune]*TrieNode
	count    int
}

func NewTrieNode() *TrieNode {
	return &TrieNode{children: make(map[rune]*TrieNode)}
}

func (t *TrieNode) Insert(word string) {
	node := t
	for _, ch := range word {
		if node.children[ch] == nil {
			node.children[ch] = NewTrieNode()
		}
		node = node.children[ch]
		node.count++
	}
}

func (t *TrieNode) CountPrefix(prefix string) int {
	node := t
	for _, ch := range prefix {
		if node.children[ch] == nil {
			return 0
		}
		node = node.children[ch]
	}
	return node.count
}

func main() {
	trie := NewTrieNode()
	words := []string{"apple", "app", "application", "banana"}
	for _, w := range words {
		trie.Insert(w)
	}
	fmt.Println(trie.CountPrefix("app"))
}

A 3

B 4

C 2

D 1

💡 Hint

Count how many words start with "app" in the list.

The words starting with "app" are "apple", "app", and "application". So the count is 3.

❓ Predict Output

intermediate

Count prefix after inserting overlapping words

What is the output of the program when counting words starting with prefix "car" after inserting "car", "card", "cart", "care", "dog"?

DSA Go

package main

import "fmt"

type TrieNode struct {
	children map[rune]*TrieNode
	count    int
}

func NewTrieNode() *TrieNode {
	return &TrieNode{children: make(map[rune]*TrieNode)}
}

func (t *TrieNode) Insert(word string) {
	node := t
	for _, ch := range word {
		if node.children[ch] == nil {
			node.children[ch] = NewTrieNode()
		}
		node = node.children[ch]
		node.count++
	}
}

func (t *TrieNode) CountPrefix(prefix string) int {
	node := t
	for _, ch := range prefix {
		if node.children[ch] == nil {
			return 0
		}
		node = node.children[ch]
	}
	return node.count
}

func main() {
	trie := NewTrieNode()
	words := []string{"car", "card", "cart", "care", "dog"}
	for _, w := range words {
		trie.Insert(w)
	}
	fmt.Println(trie.CountPrefix("car"))
}

A 1

B 3

C 4

D 5

💡 Hint

Count all words starting with "car".

Words starting with "car" are "car", "card", "cart", and "care". So count is 4.

❓ Predict Output

advanced

Output after deleting a word and counting prefix

Given a trie where words "test", "tester", "testing" are inserted, what is the output of counting prefix "test" after deleting "tester"?

DSA Go

package main

import "fmt"

type TrieNode struct {
	children map[rune]*TrieNode
	count    int
	end      int
}

func NewTrieNode() *TrieNode {
	return &TrieNode{children: make(map[rune]*TrieNode)}
}

func (t *TrieNode) Insert(word string) {
	node := t
	for _, ch := range word {
		if node.children[ch] == nil {
			node.children[ch] = NewTrieNode()
		}
		node = node.children[ch]
		node.count++
	}
	node.end++
}

func (t *TrieNode) Delete(word string) bool {
	node := t
	stack := []*TrieNode{}
	for _, ch := range word {
		if node.children[ch] == nil {
			return false
		}
		node = node.children[ch]
		stack = append(stack, node)
	}
	if node.end == 0 {
		return false
	}
	node.end--
	for i := len(stack) - 1; i >= 0; i-- {
		stack[i].count--
	}
	return true
}

func (t *TrieNode) CountPrefix(prefix string) int {
	node := t
	for _, ch := range prefix {
		if node.children[ch] == nil {
			return 0
		}
		node = node.children[ch]
	}
	return node.count
}

func main() {
	trie := NewTrieNode()
	words := []string{"test", "tester", "testing"}
	for _, w := range words {
		trie.Insert(w)
	}
	trie.Delete("tester")
	fmt.Println(trie.CountPrefix("test"))
}

A 0

B 3

C 1

D 2

💡 Hint

Deleting "tester" reduces count by 1 for prefix "test".

Initially 3 words start with "test". After deleting "tester", 2 remain: "test" and "testing".

🔧 Debug

advanced

Identify the error in prefix count function

What error will the following Go code produce when calling CountPrefix with prefix "go" if the trie is empty?

DSA Go

func (t *TrieNode) CountPrefix(prefix string) int {
	node := t
	for _, ch := range prefix {
		if node.children[ch] == nil {
			return 0
		}
		node = node.children[ch]
	}
	return node.count
}

// Assume t is an empty trie with no children

A panic: runtime error: invalid memory address or nil pointer dereference

B 0

C 1

D Compilation error: missing return statement

💡 Hint

Check if children map is initialized in empty trie.

If the trie is empty but children map is initialized (not nil), the function returns 0 safely.

❓ Predict Output

expert

Count prefix with Unicode characters

What is the output of counting prefix "猫" after inserting words "猫", "猫咪", "猫头鹰", "狗" in the trie?

DSA Go

package main

import "fmt"

type TrieNode struct {
	children map[rune]*TrieNode
	count    int
}

func NewTrieNode() *TrieNode {
	return &TrieNode{children: make(map[rune]*TrieNode)}
}

func (t *TrieNode) Insert(word string) {
	node := t
	for _, ch := range word {
		if node.children[ch] == nil {
			node.children[ch] = NewTrieNode()
		}
		node = node.children[ch]
		node.count++
	}
}

func (t *TrieNode) CountPrefix(prefix string) int {
	node := t
	for _, ch := range prefix {
		if node.children[ch] == nil {
			return 0
		}
		node = node.children[ch]
	}
	return node.count
}

func main() {
	trie := NewTrieNode()
	words := []string{"猫", "猫咪", "猫头鹰", "狗"}
	for _, w := range words {
		trie.Insert(w)
	}
	fmt.Println(trie.CountPrefix("猫"))
}

A 3

B 4

C 1

D 0

💡 Hint

Count all words starting with the Unicode character "猫".

Words starting with "猫" are "猫", "猫咪", and "猫头鹰". So count is 3.