Huffman Encoding in DSA Go - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to create a frequency map from the input string.

DSA Go

freq := make(map[rune]int)
for _, ch := range input {
    freq[ch] [1] 1
}

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

A++

B=

C+=

D--

Attempts:

3 left

💡 Hint

Common Mistakes

Using '=' instead of '+=' causes the count to reset.

Using '++' is invalid for map values in Go.

We use '+=' to increment the count of each character in the frequency map.

2fill in blank

medium

Complete the code to define the Huffman tree node struct with frequency and character fields.

DSA Go

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

func NewNode(c rune, f int) *Node {
    return &Node{char: c, freq: [1]
}

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

Achar

Bc

Cfreq

Df

Attempts:

3 left

💡 Hint

Common Mistakes

Assigning freq: c or freq: char causes type errors.

Using freq without parameter causes undefined variable error.

The frequency field should be initialized with the parameter 'f'.

3fill in blank

hard

Fix the error in the priority queue comparison function for Huffman nodes.

DSA Go

func (pq PriorityQueue) Less(i, j int) bool {
    return pq[i].freq [1] pq[j].freq
}

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

A>

B<

C==

D>=

Attempts:

3 left

💡 Hint

Common Mistakes

Using '>' reverses the priority order.

Using '==' does not define a strict ordering.

The priority queue should order nodes by increasing frequency, so use '<'.

4fill in blank

hard

Fill both blanks to build the Huffman tree by merging two smallest nodes.

DSA Go

left := heap.Pop(&pq).(*Node)
right := heap.Pop(&pq).(*Node)
merged := &Node{freq: left.freq [1] right.freq, left: left, right: [2]
heap.Push(&pq, merged)

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

A+

B-

Cright

Dleft

Attempts:

3 left

💡 Hint

Common Mistakes

Using '-' causes incorrect frequency calculation.

Assigning left instead of right to the right child pointer.

We sum frequencies with '+' and assign the right child to 'right'.

5fill in blank

hard

Fill all three blanks to generate Huffman codes recursively.

DSA Go

func generateCodes(node *Node, code string, codes map[rune]string) {
    if node == nil {
        return
    }
    if node.left == nil && node.right == nil {
        codes[[1]] = code
        return
    }
    generateCodes(node.[2], code + "[3]", codes)
    generateCodes(node.right, code + "1", codes)
}

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

Achar

Bleft

Cright

D0

Attempts:

3 left

💡 Hint

Common Mistakes

Using 'right' instead of 'left' for the first recursive call.

Appending '1' instead of '0' for left child.

We assign code to the character, then recurse left with '0' appended.

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