How would you implement compression on a text file using Huffman coding?

Question

Accepted Answer

Huffman coding is a lossless data compression algorithm that uses variable-length codes for encoding characters based on their frequencies.

1. Count the frequency of each character in the text file.
2. Build a priority queue (min-heap) of nodes, where each node represents a character and its frequency.
3. While there is more than one node in the queue, remove the two nodes with the lowest frequency.
4. Create a new internal node with these two nodes as children and a frequency equal to the sum of their frequencies.
5. Insert the new node back into the priority queue.
6. Repeat until there is only one node left, which becomes the root of the Huffman tree.
7. Traverse the tree to assign binary codes to each character (left edge = 0, right edge = 1).
8. Replace each character in the original text with its corresponding binary code to create the compressed output.

Top Software Developer Interview Questions Asked at BNY