Crack the Backend

Problem Statement

Given the frequencies of each character (or symbol), build a Huffman encoding: a prefix-free variable-length binary code that minimizes the total number of bits to encode the message. Return the minimum total bits (or the encoding tree). Prefix-free means no code word is a prefix of another.

Key Observations

Greedy (bottom-up tree): Repeatedly merge the two nodes (leaves or subtrees) with the smallest frequencies; the new node's frequency is the sum. Use a min-heap to always get the two smallest. When only one node remains, it is the root. The total bits = sum over leaves of (freq × depth) = sum of all internal node frequencies (each merge adds that sum to the total). So we can compute total bits without building the tree: while heap has ≥2 elements, poll two, add their sum to total, push the sum back.

Approach

High-level: Min-heap of frequencies. While size >= 2: a = poll, b = poll, total += a+b, offer(a+b). Return total. (Or build tree and sum freq*depth for each leaf.)

Steps: PriorityQueue of freqs. While pq.size() >= 2: int a = pq.poll(), b = pq.poll(); total += a+b; pq.offer(a+b). Return total.

Implementation

Java

public int huffman(int[] freq) {
    PriorityQueue<Integer> pq = new PriorityQueue<>();

    for (int f : freq) {
        pq.offer(f);
    }

    int total = 0;

    while (pq.size() > 1) {
        int a = pq.poll(), b = pq.poll();
        total += a + b;
        pq.offer(a + b);
    }

    return total;
}

Test Cases

Example

Input

freq = [5,9,12,13,16,45]

Expected

Min total bits

Explanation

Build Huffman tree; sum internal node values.

Complexity Analysis

Time: typically O(n) or O(n log n).
Space: O(1) or O(n).

Follow-ups

Prove greedy choice property; handle ties.