Huffman Encoding in DSA Typescript - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

What is the output of this Huffman tree frequency merge step?

Given the initial frequency list [5, 9, 12, 13, 16, 45], after the first merge step in Huffman encoding, what is the new list of frequencies?

DSA Typescript

const frequencies = [5, 9, 12, 13, 16, 45];
// First merge step merges two smallest frequencies
// What is the new frequency list after this step?

A [5, 9, 12, 13, 61]

B [5, 9, 25, 16, 45]

C [14, 12, 13, 16, 45]

D [9, 12, 13, 16, 45]

💡 Hint

Merge the two smallest frequencies by adding them and replace them with their sum.

The two smallest frequencies are 5 and 9. Adding them gives 14. Replace 5 and 9 with 14, so the new list is [14, 12, 13, 16, 45].

🧠 Conceptual

intermediate

What property does Huffman encoding guarantee about the codes?

Which property is always true for the codes generated by Huffman encoding?

A No code is a prefix of another code.

B Codes are assigned randomly to characters.

C All codes have the same length.

D Codes are always 8 bits long.

💡 Hint

Think about how Huffman codes avoid ambiguity when decoding.

Huffman codes are prefix-free, meaning no code is a prefix of another. This ensures unique decoding.

🔧 Debug

advanced

What error occurs in this TypeScript Huffman tree node creation?

Consider this TypeScript snippet for creating a Huffman tree node: ```typescript class Node { freq: number; left?: Node; right?: Node; constructor(freq: number, left?: Node, right?: Node) { this.freq = freq; this.left = left; this.right = right; } } const node = new Node(); ``` What error will this code produce?

DSA Typescript

class Node {
  freq: number;
  left?: Node;
  right?: Node;
  constructor(freq: number, left?: Node, right?: Node) {
    this.freq = freq;
    this.left = left;
    this.right = right;
  }
}

const node = new Node();

A Error: Expected 1-3 arguments, but got 0.

B Error: Property 'freq' is missing in type '{}'.

C No error, node created with freq=0.

D Error: Cannot assign undefined to 'freq'.

💡 Hint

Check the constructor parameters and how you call it.

The constructor requires at least one argument 'freq'. Calling new Node() without arguments causes an error about missing arguments.

🚀 Application

advanced

How many bits are saved by Huffman encoding this string?

Given the string 'aaabbc', frequencies are: a=3, b=2, c=1. Using Huffman encoding, how many bits are saved compared to fixed 2-bit encoding per character?

A 4 bits saved

B 3 bits saved

C 5 bits saved

D 6 bits saved

💡 Hint

Calculate total bits with fixed length and with Huffman codes, then find the difference.

Fixed length: 6 chars * 2 bits = 12 bits. Huffman codes: a=0 (1 bit), b=10 (2 bits), c=11 (2 bits). Total bits = 3*1 + 2*2 + 1*2 = 3 + 4 + 2 = 9 bits. Bits saved = 12 - 9 = 3 bits.

❓ Predict Output

expert

What is the Huffman code for character 'd' after building this tree?

Given the frequency map {a: 5, b: 9, c: 12, d: 13, e: 16, f: 45}, after building the Huffman tree, what is the code for 'd'?

DSA Typescript

/*
Frequencies: a=5, b=9, c=12, d=13, e=16, f=45
Build Huffman tree and find code for 'd'.
*/

A '010'

B '011'

C '100'

D '101'

💡 Hint

Build the tree step-by-step and track the path to 'd' (left=0, right=1).

After building the Huffman tree for these frequencies, 'd' gets the code '101'.

Practice

1. What is the main purpose 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 goal

   Huffman Encoding aims to reduce the total bits used by giving shorter codes to frequent characters.

2. Step 2: Compare options with this goal

   Only To assign shorter codes to more frequent characters matches this goal. Others describe different or incorrect purposes.

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 in Huffman [OK]

Common Mistakes:

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

2. Which TypeScript data structure is best suited to build the priority queue for Huffman Encoding?

easy

A. Array with manual sorting

B. Min-Heap

C. Set

D. Map

Solution

1. Step 1: Identify priority queue needs

   Huffman Encoding requires repeatedly extracting the smallest frequency node efficiently.

2. Step 2: Choose data structure for efficient min extraction

   Min-Heap allows quick access and removal of the smallest element, ideal for this use.

3. Final Answer:

   Min-Heap -> Option B

4. Quick Check:

   Priority queue = Min-Heap for Huffman [OK]

Hint: Use Min-Heap for efficient smallest element extraction [OK]

Common Mistakes:

• Using Set which has no order
• Using Map which is key-value, not priority queue
• Using Array without sorting is inefficient

3. What is the output Huffman code for characters {a:5, b:9, c:12, d:13, e:16, f:45} after building the Huffman tree?

medium

A. { 'f': '1', 'c': '00', 'd': '01', 'a': '100', 'b': '101', 'e': '110' }

B. { 'a': '0', 'b': '10', 'c': '110', 'd': '1110', 'e': '1111', 'f': '101' }

C. { 'f': '0', 'c': '100', 'd': '101', 'a': '1100', 'b': '1101', 'e': '111' }

D. { 'a': '111', 'b': '110', 'c': '10', 'd': '0', 'e': '101', 'f': '100' }

Solution

1. Step 1: Build Huffman tree from frequencies

   Combine lowest frequencies stepwise: (a=5,b=9)->14, (c=12,d=13)->25, then combine 14 and 16 (e) and so on, finally f=45 is highest frequency with shortest code.

2. Step 2: Assign codes from tree paths

   Left edges as '0', right edges as '1' produce codes: f='0', c='100', d='101', a='1100', b='1101', e='111'.

3. Final Answer:

   { 'f': '0', 'c': '100', 'd': '101', 'a': '1100', 'b': '1101', 'e': '111' } -> Option C

4. Quick Check:

   Highest freq 'f' gets shortest code '0' [OK]

Hint: Highest frequency gets shortest code '0' in Huffman [OK]

Common Mistakes:

• Assigning codes without building tree
• Mixing left/right edge bits
• Ignoring frequency order

4. Given this TypeScript snippet for Huffman tree node insertion, what is the bug?

class Node {
  constructor(public char: string | null, public freq: number, public left: Node | null = null, public right: Node | null = null) {}
}

function insertNode(queue: Node[], node: Node) {
  queue.push(node);
  queue.sort((a, b) => a.freq - b.freq);
}

// Usage
const queue: Node[] = [];
insertNode(queue, new Node('a', 5));
insertNode(queue, new Node('b', 9));
insertNode(queue, new Node(null, 14));

medium

A. Sorting after push is inefficient; use a Min-Heap instead

B. Node constructor missing type annotations

C. Function insertNode should remove duplicates

D. queue.sort comparator should be reversed

Solution

1. Step 1: Analyze insertNode function

   It pushes a node then sorts the entire queue array by frequency each time.

2. Step 2: Identify inefficiency

   Sorting the whole array on every insertion is inefficient for large data; a Min-Heap is better for priority queue operations.

3. Final Answer:

   Sorting after push is inefficient; use a Min-Heap instead -> Option A

4. Quick Check:

   Priority queue needs efficient insert and extract [OK]

Hint: Use Min-Heap, not array sort, for priority queue [OK]

Common Mistakes:

• Thinking sorting order is wrong
• Missing inefficiency of sorting whole array
• Confusing type annotations as bug

5. You have a string "aaabbc" and want to encode it using Huffman Encoding. Which of the following is the correct Huffman code assignment and encoded bit string?

hard

A. Codes: {a:'0', b:'10', c:'11'}, Encoded: '000101011'

B. Codes: {a:'10', b:'0', c:'11'}, Encoded: '101010011'

C. Codes: {a:'0', b:'11', c:'10'}, Encoded: '00011110'

D. Codes: {a:'1', b:'0', c:'10'}, Encoded: '1110010'

Solution

1. Step 1: Calculate frequencies

   String "aaabbc" has frequencies: a=3, b=2, c=1.

2. Step 2: Build Huffman tree and assign codes

   Lowest freq c=1 and b=2 combine first, then with a=3. Assign codes: a='0', b='10', c='11'.

3. Step 3: Encode string using codes

   Encoding "aaabbc" = a(3 times) '0 0 0', b(2 times) '10 10', c(1 time) '11' -> '000101011'.

4. Final Answer:

   Codes: {a:'0', b:'10', c:'11'}, Encoded: '000101011' -> Option A

5. Quick Check:

   Freq order a>b>c matches codes and encoding [OK]

Hint: Encode by replacing chars with shortest codes from tree [OK]

Common Mistakes:

• Mixing code assignments
• Encoding with wrong code bits
• Ignoring frequency order in code assignment