Huffman Encoding in DSA Java - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to create a priority queue for Huffman nodes.

DSA Java

PriorityQueue<Node> pq = new PriorityQueue<>([1]);

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

A(a, b) -> a.freq - b.freq

B(a, b) -> b.freq - a.freq

C(a, b) -> a.freq + b.freq

D(a, b) -> a.freq * b.freq

Attempts:

3 left

💡 Hint

Common Mistakes

Using a comparator that orders frequencies descending.

Using addition or multiplication instead of subtraction.

The priority queue should order nodes by frequency ascending, so the comparator subtracts frequencies.

2fill in blank

medium

Complete the code to build the Huffman tree by combining two lowest frequency nodes.

DSA Java

Node left = pq.poll();
Node right = pq.poll();
Node parent = new Node(null, left.freq + right.freq);
parent.left = left;
parent.right = right;
pq.[1](parent);

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

Apoll

Badd

Cpeek

Dremove

Attempts:

3 left

💡 Hint

Common Mistakes

Using poll() which removes instead of adding.

Using peek() which only views the element.

After creating the parent node, it must be added back to the priority queue.

3fill in blank

hard

Fix the error in the recursive method to generate Huffman codes.

DSA Java

void generateCodes(Node root, String code) {
  if (root == null) return;
  if (root.ch != null) {
    codes.put(root.ch, code);
  } else {
    generateCodes(root.left, code [1] "0");
    generateCodes(root.right, code [1] "1");
  }
}

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

A+

B-

C*

D/

Attempts:

3 left

💡 Hint

Common Mistakes

Using arithmetic operators other than + for strings.

Not concatenating the code string properly.

To build the code string, concatenate '0' or '1' to the current code using + operator.

4fill in blank

hard

Fill both blanks to create a map of character frequencies from a string.

DSA Java

Map<Character, Integer> freqMap = new HashMap<>();
for (char c : text.toCharArray()) {
  freqMap.put(c, freqMap.getOrDefault(c, [1]) [2] 1);
}

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

A0

B1

C+

D-

Attempts:

3 left

💡 Hint

Common Mistakes

Using 1 as default causes off-by-one errors.

Using subtraction instead of addition.

If character not present, default count is 0, then add 1 to update frequency.

5fill in blank

hard

Fill all three blanks to create a Huffman code map filtering only codes with length > 0.

DSA Java

Map<Character, String> filteredCodes = codes.entrySet().stream()
  .filter(e -> e.getValue().length() [1] 0)
  .collect(Collectors.toMap(
    e -> e.getKey(),
    e -> e.getValue().[2](),
    (a, b) -> a, [3]));

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

A>

BtoUpperCase

CHashMap::new

D<

Attempts:

3 left

💡 Hint

Common Mistakes

Using < instead of > in filter.

Forgetting parentheses on toUpperCase method.

Not providing a map supplier in collect.

Filter codes with length > 0, convert values to uppercase, collect into a new HashMap.

Practice

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

easy

A. To sort characters alphabetically

B. To assign shorter codes to more frequent characters

C. To encrypt data for security

D. To assign equal length codes to all characters

Solution

1. Step 1: Understand Huffman Encoding goal

   Huffman Encoding aims to reduce the total bits used by assigning shorter codes to characters that appear more often.

2. Step 2: Compare options with goal

   Only To assign shorter codes to more frequent characters matches this goal. Options A, B, and C do not describe Huffman Encoding correctly.

3. Final Answer:

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

4. Quick Check:

   Huffman Encoding = shorter codes for frequent chars [OK]

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

Common Mistakes:

• Thinking Huffman assigns equal length codes
• Confusing Huffman with encryption
• Assuming it sorts characters alphabetically

2. Which Java data structure is commonly used to build the Huffman tree efficiently?

easy

A. PriorityQueue

B. HashMap

C. ArrayList

D. Stack

Solution

1. Step 1: Identify data structure for minimum frequency extraction

   Huffman tree construction repeatedly extracts two nodes with the smallest frequencies.

2. Step 2: Match data structure to this need

   A PriorityQueue efficiently provides the smallest element each time, making it ideal for this task.

3. Final Answer:

   PriorityQueue -> Option A

4. Quick Check:

   Minimum extraction = PriorityQueue [OK]

Hint: Use PriorityQueue for smallest frequency extraction [OK]

Common Mistakes:

• Using ArrayList which is not efficient for min extraction
• Choosing HashMap which stores key-value pairs, not order
• Selecting Stack which is LIFO, not suitable here

3. What is the output Huffman code for characters given frequencies: A=5, B=9, C=12, D=13, E=16, F=45? (Assuming standard Huffman algorithm)

medium

A. A: 111, B: 110, C: 101, D: 100, E: 0, F: 11

B. A: 0, B: 111, C: 110, D: 10, E: 101, F: 100

C. A: 100, B: 101, C: 110, D: 111, E: 0, F: 11

D. A: 1100, B: 1101, C: 100, D: 101, E: 111, F: 0

Solution

1. Step 1: Build Huffman tree from frequencies

   Combine lowest frequencies stepwise: (A=5, B=9) -> 14, then combine with C=12, etc., building tree with F=45 as root's child.

2. Step 2: Assign codes from tree paths

   F gets shortest code '0' (highest freq). A and B get longer codes starting with '1100' and '1101' respectively.

3. Final Answer:

   A: 1100, B: 1101, C: 100, D: 101, E: 111, F: 0 -> Option D

4. Quick Check:

   Lowest freq get longest codes = A: 1100, B: 1101, C: 100, D: 101, E: 111, F: 0 [OK]

Hint: Lowest freq get longest codes, highest freq shortest [OK]

Common Mistakes:

• Assigning shortest codes to low frequency chars
• Mixing code assignments without tree structure
• Ignoring frequency order in code lengths

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

PriorityQueue<Node> pq = new PriorityQueue<>();
pq.add(new Node('a', 5));
pq.add(new Node('b', 9));
Node left = pq.poll();
Node right = pq.poll();
Node parent = new Node(null, left.freq + right.freq);
parent.left = left;
parent.right = right;
pq.add(parent);

medium

A. Node class must implement Comparable for PriorityQueue

B. Cannot add null character to Node

C. PriorityQueue should be initialized with capacity

D. Must poll three nodes before creating parent

Solution

1. Step 1: Check PriorityQueue usage

   PriorityQueue requires elements to be comparable or a comparator provided to order nodes by frequency.

2. Step 2: Verify Node class implementation

   If Node does not implement Comparable or no comparator is given, pq.poll() will throw runtime error.

3. Final Answer:

   Node class must implement Comparable for PriorityQueue -> Option A

4. Quick Check:

   PriorityQueue needs Comparable nodes [OK]

Hint: Ensure Node implements Comparable for PriorityQueue [OK]

Common Mistakes:

• Ignoring Comparable interface requirement
• Thinking null character is invalid here
• Assuming PriorityQueue needs capacity argument

5. Given a string "abbcccdddd", how many bits will Huffman Encoding save compared to fixed-length 3-bit encoding per character?

hard

A. 7 bits saved

B. 10 bits saved

C. 11 bits saved

D. 15 bits saved

Solution

1. Step 1: Calculate fixed-length bits

   String length is 10, fixed-length 3 bits per char, total bits = 10*3 = 30 bits.

2. Step 2: Calculate Huffman bits

   Frequencies: a=1, b=2, c=3, d=4. Huffman codes: a:100 (3 bits), b:101 (3), c:11 (2), d:0 (1). Total bits = (1*3) + (2*3) + (3*2) + (4*1) = 3 + 6 + 6 + 4 = 19 bits.

3. Step 3: Calculate bits saved

   Bits saved = 30 - 19 = 11 bits.

4. Final Answer:

   11 bits saved -> Option C

5. Quick Check:

   Fixed 30 bits - Huffman 19 bits = 11 bits saved [OK]

Hint: Calculate fixed bits minus Huffman bits for savings [OK]

Common Mistakes:

• Not counting frequencies correctly
• Using wrong bit length for fixed encoding
• Miscomputing total Huffman bits