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.

Practice

1. What does the problem "Count Words with Given Prefix" ask you to do?

easy

A. Count the total number of characters in all words

B. Find the longest word in a list

C. Count how many words in a list start with a specific prefix

D. Sort the words alphabetically

Solution

1. Step 1: Understand the problem statement

   The problem asks to find how many words begin with a given prefix string.

2. Step 2: Identify the key operation

   We need to check each word and count those that start with the prefix.

3. Final Answer:

   Count how many words in a list start with a specific prefix -> Option C

4. Quick Check:

   Counting words by prefix = Count how many words in a list start with a specific prefix [OK]

Hint: Look for words starting exactly with the prefix [OK]

Common Mistakes:

• Confusing prefix with substring anywhere in word
• Counting total words instead of filtered ones
• Ignoring case sensitivity if required

2. Which of the following Go code snippets correctly checks if a word starts with a given prefix pref?

easy

A. strings.HasPrefix(word, pref)

B. strings.Contains(word, pref)

C. word[:len(pref)] == pref

D. word == pref

Solution

1. Step 1: Recall Go standard library functions

   strings.HasPrefix(word, pref) returns true if word starts with pref.

2. Step 2: Compare other options

   strings.Contains checks anywhere, slicing may panic if prefix longer, equality checks full word.

3. Final Answer:

   strings.HasPrefix(word, pref) -> Option A

4. Quick Check:

   Use HasPrefix for prefix check [OK]

Hint: Use strings.HasPrefix for safe prefix check [OK]

Common Mistakes:

• Using strings.Contains which checks anywhere in word
• Slicing without length check causing runtime panic
• Comparing whole word instead of prefix

3. What is the output of the following Go code?

package main
import (
  "fmt"
  "strings"
)
func countPrefix(words []string, prefix string) int {
  count := 0
  for _, w := range words {
    if strings.HasPrefix(w, prefix) {
      count++
    }
  }
  return count
}
func main() {
  words := []string{"apple", "app", "application", "banana", "apply"}
  fmt.Println(countPrefix(words, "app"))
}

medium

A. 4

B. 2

C. 3

D. 5

Solution

1. Step 1: Identify words starting with "app"

   Words: "apple", "app", "application", "banana", "apply". "banana" does not start with "app".

2. Step 2: Count matching words

   Matching words: "apple", "app", "application", "apply" -> 4 words.

3. Final Answer:

   4 -> Option A

4. Quick Check:

   Count of words starting with "app" = 4 [OK]

Hint: Count words starting exactly with prefix using HasPrefix [OK]

Common Mistakes:

• Counting "banana" incorrectly
• Off-by-one error in counting
• Misreading prefix length

4. The following Go code is intended to count words starting with a prefix but causes a runtime error. What is the error?

func countPrefix(words []string, prefix string) int {
  count := 0
  for _, w := range words {
    if w[:len(prefix)] == prefix {
      count++
    }
  }
  return count
}

medium

A. No error, code works fine

B. Index out of range panic if word shorter than prefix

C. Logical error: counts words containing prefix anywhere

D. Syntax error due to missing import

Solution

1. Step 1: Analyze slicing operation

   The code slices w[:len(prefix)] without checking if w is long enough.

2. Step 2: Identify runtime error cause

   If w is shorter than prefix, slicing causes index out of range panic.

3. Final Answer:

   Index out of range panic if word shorter than prefix -> Option B

4. Quick Check:

   Slicing without length check causes panic [OK]

Hint: Check word length before slicing prefix [OK]

Common Mistakes:

• Ignoring length check before slicing
• Assuming code compiles without imports
• Confusing prefix check with substring check

5. You have a list of words and want to count how many start with each prefix from a list of prefixes. Which approach is best for efficient counting in Go?

hard

A. Use strings.Contains to check prefix in each word

B. For each prefix, loop over all words and count matches

C. Sort words and use binary search for each prefix

D. Build a trie from words, then query counts for each prefix

Solution

1. Step 1: Understand the problem scale

   Counting for many prefixes over many words needs efficiency.

2. Step 2: Compare approaches

   Looping over all words for each prefix is slow (O(P*W)). Sorting + binary search helps but trie allows prefix counting efficiently.

3. Step 3: Choose best data structure

   Trie stores words by prefix, enabling fast prefix count queries.

4. Final Answer:

   Build a trie from words, then query counts for each prefix -> Option D

5. Quick Check:

   Trie enables efficient prefix counting [OK]

Hint: Use trie for fast prefix count queries [OK]

Common Mistakes:

• Using nested loops causing slow performance
• Using strings.Contains which is incorrect for prefix
• Ignoring data structure benefits