Huffman Encoding in DSA Go - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Huffman Tree Construction

What is the output of the following Go code that builds a Huffman tree and prints the root node frequency?

DSA Go

package main

import (
	"container/heap"
	"fmt"
)

type Node struct {
	char  rune
	freq  int
	left  *Node
	right *Node
}

type PriorityQueue []*Node

func (pq PriorityQueue) Len() int { return len(pq) }
func (pq PriorityQueue) Less(i, j int) bool { return pq[i].freq < pq[j].freq }
func (pq PriorityQueue) Swap(i, j int) { pq[i], pq[j] = pq[j], pq[i] }
func (pq *PriorityQueue) Push(x interface{}) { *pq = append(*pq, x.(*Node)) }
func (pq *PriorityQueue) Pop() interface{} {
	n := len(*pq)
	item := (*pq)[n-1]
	*pq = (*pq)[:n-1]
	return item
}

func buildHuffmanTree(freqMap map[rune]int) *Node {
	pq := &PriorityQueue{}
	heap.Init(pq)
	for ch, freq := range freqMap {
		heap.Push(pq, &Node{char: ch, freq: freq})
	}
	for pq.Len() > 1 {
		left := heap.Pop(pq).(*Node)
		right := heap.Pop(pq).(*Node)
		merged := &Node{freq: left.freq + right.freq, left: left, right: right}
		heap.Push(pq, merged)
	}
	return heap.Pop(pq).(*Node)
}

func main() {
	freqMap := map[rune]int{'a': 5, 'b': 9, 'c': 12, 'd': 13, 'e': 16, 'f': 45}
	root := buildHuffmanTree(freqMap)
	fmt.Println(root.freq)
}

A 100

B 45

C 16

D 50

💡 Hint

Sum all frequencies to find the root node frequency.

The root node frequency is the sum of all character frequencies: 5+9+12+13+16+45 = 100.

🧠 Conceptual

intermediate

Huffman Encoding Bit Length Calculation

Given the frequencies {'a': 3, 'b': 2, 'c': 6, 'd': 8}, what is the total number of bits required to encode the string "abcd" repeated 5 times using Huffman encoding?

A 50

B 45

C 35

D 40

💡 Hint

Calculate the Huffman codes for each character, then multiply by their frequencies in the repeated string.

The Huffman codes assign shorter codes to higher frequency chars. After building the tree, the total bits for 5 repetitions of "abcd" (20 chars) is 45 bits.

🔧 Debug

advanced

Identify the Error in Huffman Encoding Implementation

What error will the following Go code produce when trying to build a Huffman tree?

DSA Go

package main

import (
	"container/heap"
	"fmt"
)

type Node struct {
	char  rune
	freq  int
	left  *Node
	right *Node
}

type PriorityQueue []*Node

func (pq PriorityQueue) Len() int { return len(pq) }
func (pq PriorityQueue) Less(i, j int) bool { return pq[i].freq > pq[j].freq }
func (pq PriorityQueue) Swap(i, j int) { pq[i], pq[j] = pq[j], pq[i] }
func (pq *PriorityQueue) Push(x interface{}) { *pq = append(*pq, x.(*Node)) }
func (pq *PriorityQueue) Pop() interface{} {
	n := len(*pq)
	item := (*pq)[n-1]
	*pq = (*pq)[:n-1]
	return item
}

func buildHuffmanTree(freqMap map[rune]int) *Node {
	pq := &PriorityQueue{}
	heap.Init(pq)
	for ch, freq := range freqMap {
		heap.Push(pq, &Node{char: ch, freq: freq})
	}
	for pq.Len() > 1 {
		left := heap.Pop(pq).(*Node)
		right := heap.Pop(pq).(*Node)
		merged := &Node{freq: left.freq + right.freq, left: left, right: right}
		heap.Push(pq, merged)
	}
	return heap.Pop(pq).(*Node)
}

func main() {
	freqMap := map[rune]int{'a': 5, 'b': 9, 'c': 12}
	root := buildHuffmanTree(freqMap)
	fmt.Println(root.freq)
}

A The heap will behave as a max-heap, causing incorrect tree construction

B Syntax error due to missing import

C Runtime panic due to nil pointer dereference

D Compilation error due to wrong method signatures

💡 Hint

Check the Less function in the priority queue implementation.

The Less function uses '>' which makes the heap a max-heap, but Huffman requires a min-heap to combine lowest frequencies first. This causes incorrect tree construction.

📝 Syntax

advanced

Identify the Syntax Error in Huffman Encoding Code

Which option contains the syntax error in this Go code snippet for Huffman encoding?

DSA Go

type Node struct {
	char  rune
	freq  int
	left  *Node
	right *Node
}

func buildHuffmanTree(freqMap map[rune]int) *Node {
	pq := &PriorityQueue{}
	heap.Init(pq)
	for ch, freq := range freqMap {
		heap.Push(pq, &Node{char: ch, freq: freq})
	}
	for pq.Len() > 1 {
		left := heap.Pop(pq).(*Node)
		right := heap.Pop(pq).(*Node)
		merged := &Node{freq: left.freq + right.freq, left: left, right: right}
		heap.Push(pq, merged)
	}
	return heap.Pop(pq).(*Node)
}

A Incorrect struct field names in Node definition

B Using := instead of = in for loop

C Missing import "container/heap" statement

D Missing parentheses in function call heap.Init

💡 Hint

Check the imports needed for heap operations.

The code uses heap.Init and heap.Push but does not import "container/heap", causing a syntax error.

🚀 Application

expert

Calculate Huffman Encoding Output for Given Frequencies

Given the frequencies {'x': 10, 'y': 15, 'z': 30, 'w': 45}, what is the Huffman code length for character 'y' after building the Huffman tree?

A 1 bit

B 2 bits

C 4 bits

D 3 bits

💡 Hint

Build the Huffman tree step-by-step and count the depth of 'y'.

The Huffman tree merges lowest frequencies first. 'y' with frequency 15 ends up at depth 3, so its code length is 3 bits.

Practice

1. What is the main goal of Huffman Encoding in data compression?

easy

A. To sort characters alphabetically

B. To assign equal length codes to all characters

C. To encrypt data for security

D. To assign shorter codes to more frequent characters

Solution

1. Step 1: Understand Huffman Encoding purpose

   Huffman Encoding compresses data by using variable-length codes based on character frequency.

2. Step 2: Identify code assignment rule

   More frequent characters get shorter codes to reduce overall data size.

3. Final Answer:

   To assign shorter codes to more frequent characters -> Option D

4. Quick Check:

   Huffman Encoding = shorter codes for frequent chars [OK]

Hint: Remember: frequent chars get shorter codes [OK]

Common Mistakes:

• Thinking all codes have same length
• Confusing compression with encryption
• Assuming alphabetical order affects codes

2. Which of the following Go code snippets correctly declares a priority queue for Huffman nodes using container/heap?

easy

A. type HuffmanNode struct {char string; freq float64}; var pq []HuffmanNode

B. var pq []int = make([]int, 0)

C. type HuffmanNode struct {char rune; freq int}; type PriorityQueue []*HuffmanNode

D. var pq map[rune]int = make(map[rune]int)

Solution

1. Step 1: Identify correct struct for Huffman node

   HuffmanNode should have a character (rune) and frequency (int).

2. Step 2: Check priority queue declaration

   PriorityQueue should be a slice of pointers to HuffmanNode for heap operations.

3. Final Answer:

   type HuffmanNode struct {char rune; freq int}; type PriorityQueue []*HuffmanNode -> Option C

4. Quick Check:

   Priority queue = slice of HuffmanNode pointers [OK]

Hint: Use slice of pointers for priority queue [OK]

Common Mistakes:

• Using map instead of slice for priority queue
• Using wrong data types for char or freq
• Declaring slice of values instead of pointers

3. Given the frequencies: {'a': 5, 'b': 9, 'c': 12, 'd': 13}, what is the Huffman code for 'a' after building the tree?

medium

A. 10

B. 00

C. 111

D. 110

Solution

1. Step 1: Build Huffman tree from frequencies

   Combine lowest frequencies: 5('a') + 9('b') = 14, then combine 12('c') + 13('d') = 25, then combine 14 + 25 = 39.

2. Step 2: Assign codes from tree

   'a' is in the left subtree of the first combined node, so it gets code '10' (left-right).

3. Final Answer:

   10 -> Option A

4. Quick Check:

   'a' = code '10' [OK]

Hint: Lowest freq chars get codes starting with 1 or 0 depending on tree [OK]

Common Mistakes:

• Assigning longer codes to lowest freq chars
• Mixing up left and right branches
• Ignoring tree structure when assigning codes

4. Identify the error in this Go snippet for building a Huffman tree:

func buildTree(freq map[rune]int) *Node {
  pq := &PriorityQueue{}
  heap.Init(pq)
  for c, f := range freq {
    heap.Push(pq, &Node{char: c, freq: f})
  }
  for pq.Len() > 1 {
    left := heap.Pop(pq).(*Node)
    right := heap.Pop(pq).(*Node)
    merged := &Node{freq: left.freq + right.freq, left: left, right: right}
    heap.Push(pq, merged)
  }
  return heap.Pop(pq).(*Node)
}

medium

A. PriorityQueue must implement heap.Interface methods

B. freq map keys should be string, not rune

C. heap.Init should be called after pushing elements

D. Cannot push pointers to heap

Solution

1. Step 1: Check PriorityQueue usage with heap

   Go's heap requires the PriorityQueue type to implement heap.Interface methods Len, Less, Swap, Push, and Pop.

2. Step 2: Identify missing implementation

   If PriorityQueue does not implement these methods, heap.Init and heap.Push will cause runtime errors.

3. Final Answer:

   PriorityQueue must implement heap.Interface methods -> Option A

4. Quick Check:

   heap.Interface implementation required [OK]

Hint: Always implement heap.Interface for priority queues [OK]

Common Mistakes:

• Using wrong key type in freq map
• Calling heap.Init too early or late
• Trying to push non-pointer values

5. You have a string "aaabbc" and want to encode it using Huffman Encoding. Which of the following steps correctly describes how to build the Huffman tree and generate codes?

hard

A. Sort characters alphabetically, assign fixed-length codes, encode string

B. Count frequencies, build min-heap, merge nodes until one tree, assign codes from tree

C. Assign random codes to characters, then compress string

D. Use frequency to assign codes but skip building tree

Solution

1. Step 1: Count character frequencies

   For "aaabbc", frequencies are: 'a':3, 'b':2, 'c':1.

2. Step 2: Build min-heap and merge nodes

   Create nodes for each char, push into min-heap, merge two smallest nodes repeatedly until one tree remains.

3. Step 3: Assign codes from the tree

   Traverse tree assigning '0' for left and '1' for right edges to generate prefix codes.

4. Final Answer:

   Count frequencies, build min-heap, merge nodes until one tree, assign codes from tree -> Option B

5. Quick Check:

   Huffman = freq count + min-heap + merge + code assign [OK]

Hint: Follow frequency -> min-heap -> merge -> code assign steps [OK]

Common Mistakes:

• Skipping tree building step
• Assigning fixed-length codes ignoring frequency
• Using random codes without structure