Register for our webinar

### How to Nail your next Technical Interview

1 hour
1
Enter details
2
Select webinar slot
*Invalid First Name
*Invalid Last Name
*Invalid Phone Number
Step 1
Step 2
Congratulations!
You have registered for our webinar
Oops! Something went wrong while submitting the form.
1
Enter details
2
Select webinar slot
Step 1
Step 2
Confirmed
You are scheduled with Interview Kickstart.
Redirecting...
Oops! Something went wrong while submitting the form.

## You may be missing out on a 66.5% salary hike*

### Nick Camilleri

Head of Career Skills Development & Coaching
*Based on past data of successful IK students
Help us know you better!

## How many years of coding experience do you have?

Oops! Something went wrong while submitting the form.

### Attend our Free Webinar on How to Nail Your Next Technical Interview

WEBINAR +LIVE Q&A

## How To Nail Your Next Tech Interview

Hosted By
Ryan Valles
Founder, Interview Kickstart
Our tried & tested strategy for cracking interviews
How FAANG hiring process works
The 4 areas you must prepare for
How you can accelerate your learnings

# ? Huffman Coding - Greedy Algorithm

### Attend our Free Webinar on How to Nail Your Next Technical Interview

WEBINAR +LIVE Q&A

## How To Nail Your Next Tech Interview

Hosted By
Ryan Valles
Founder, Interview Kickstart
Our tried & tested strategy for cracking interviews
How FAANG hiring process works
The 4 areas you must prepare for
How you can accelerate your learnings

# ? Huffman Coding - Greedy Algorithm

# Introduction to Huffman Coding Huffman Coding is a data compression algorithm created by [David A. Huffman](https://en.wikipedia.org/wiki/David_A._Huffman) in 1952. It is an **entropy-based** algorithm that uses a *greedy approach* to generate a prefix-free code for a given set of symbols and associated probability/frequency of occurrence. The generated code is optimal in the sense that it minimizes the expected length of the encoded message. Huffman coding works by assigning a unique binary string to each character in a given dataset. The codes are assigned in such a way that the length of the code is inversely proportional to the frequency of occurrence of the character. Characters that occur more often in the dataset are assigned shorter codes than those that occur less frequently. The resulting string of 0s and 1s, when combined with a Huffman tree, can be used to decode the encoded message. Huffman coding is widely used in many applications, such as data compression, data transmission and image processing. It is also used in many communication protocols, such as GSM, JPEG and MPEG.

## Worried About Failing Tech Interviews?

Attend our webinar on
"How to nail your next tech interview" and learn

Hosted By
Ryan Valles
Founder, Interview Kickstart
Our tried & tested strategy for cracking interviews
How FAANG hiring process works
The 4 areas you must prepare for
How you can accelerate your learnings
Huffman Coding is a Greedy Algorithm used for compressing data. It works by assigning variable length codes to characters, which allows for a more efficient representation of the data. The algorithm works by creating a binary tree, with the least frequent characters at the deepest level of the tree. We then traverse the tree, creating a code for each character based on the path from the root of the tree to the character's node. ## Sample Code ``` // Create a HashMap to store character frequencies Map frequencies = new HashMap<>(); // Populate the HashMap with character frequencies frequencies.put('a', 5); frequencies.put('b', 9); frequencies.put('c', 12); frequencies.put('d', 13); frequencies.put('e', 16); frequencies.put('f', 45); // Create a Priority Queue to store nodes of the Huffman tree PriorityQueue pq = new PriorityQueue(); // Create Huffman tree nodes for each character and add them to the Priority Queue for (Map.Entry entry : frequencies.entrySet()) { Node node = new Node(entry.getKey(), entry.getValue()); pq.add(node); } // Build the Huffman tree while (pq.size() > 1) { // Extract two nodes with the lowest frequency Node left = pq.poll(); Node right = pq.poll(); // Create a new internal node with the frequency of the two nodes int sum = left.frequency + right.frequency; Node parent = new Node(null, sum); // Set the two extracted nodes as children of the new internal node parent.left = left; parent.right = right; // Add the new internal node to the Priority Queue pq.add(parent); } // Traverse the tree to extract the Huffman codes Map codes = new HashMap<>(); extractCodes(pq.poll(), "", codes); // Print the Huffman codes System.out.println(codes); // Recursive function to traverse the tree and extract the codes public void extractCodes(Node node, String code, Map codes) { if (node == null) { return; } if (node.character != null) { codes.put(node.character, code); } extractCodes(node.left, code + "0", codes); extractCodes(node.right, code + "1", codes); } ```