Two Sigma / VO 面试真题解析：Document Compressor，哈夫曼编码与优先队列

Implement 2 functions:

• A'= encode(A) takes in a string (ASCII only) that represents the document A, and returns the binary string representation of the encoded string A'.
• A = decode(A') takes in the output of encode() – A', and returns the original string A.

For simplicity, we expect A' to be a string of 0s and 1s instead of the actual compressed bytes.

You can expect the call sequence to be encode(A), decode(A'), encode(B), decode(B').

You don’t need to worry about someone calling encode(A), encode(B), decode(A'), decode(B').

Compression algorithm

Suppose you have "aaaaabbbbcccdde". You can build a tree like below such that a = 00, b = 01, c = 11, d = 100, e = 101.

After encoding, it becomes "000000000001010101111111100100101", which is only 33 bits compared to the original 15 * 8 = 120 bits.

To construct a tree like above, you start by pairing the least frequent characters first, then build the tree upwards. There can be multiple valid trees. We aren’t requiring the absolute best compression.

Your implementation is considered good as long as it’s:

• correct: successfully recovers to the original string A
• effective: the compressed string is conceptually shorter than the original string: len(A') < len(A) * 8

这道题本质上是在实现一个简化版的哈夫曼编码压缩器：先统计字符频次，用最小堆不断合并出现次数最少的两个节点，构造一棵前缀树，再为左右子树分别分配 0 和 1。编码时根据这棵树把原字符串转成比特串；解码时则沿树逐位下行，遇到叶子就还原出一个字符。题目允许多种合法树形，因此不要求唯一最优压缩率，但必须保证编码与解码能互相还原，并且压缩后的表示在概念上比原始 ASCII 更短。实现时通常需要在 encode 和 decode 之间保存同一份树结构，常见做法是用优先队列构建哈夫曼树，再配合递归或栈生成字符到编码的映射。