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'.