## Problem Arithmetic coding compresses a message into a single number in `[0, 1)` based on character probabilities. Given a symbol frequency table and a message, implement an encoder and decoder. ```python class ArithmeticCoder: def __init__(self, frequencies: dict[str, int]): ... def encode(self, message: str) -> float: # returns a number in [0,1) def decode(self, encoded: float, length: int) -> str: ``` ## Example ``` frequencies = {"a": 3, "b": 2, "c": 1} # total = 6 # Probability ranges: # a: [0, 0.5) # b: [0.5, 0.833) # c: [0.833, 1.0) Encode "ab": Start: [0, 1) After 'a': [0, 0.5) After 'b': [0 + 0.5*0.5, 0 + 0.5*0.833) = [0.25, 0.4165) Output: any value in [0.25, 0.4165), e.g. 0.3 coder.decode(0.3, 2) -> "ab" ``` ## Follow-ups 1. Floating-point precision limits the message length. How does integer arithmetic coding solve this? 2. How does arithmetic coding compare to Huffman coding in compression ratio? 3. How do you handle symbols not seen in the frequency table (zero-probability problem)?

InterviewDB Experience

Arithmetic Encoding: Implement Arithmetic Coding for Lossless Data Compression

phone

Interview Experience

Problem Arithmetic coding compresses a message into a single number in [0, 1) based on character probabilities. Given a symbol frequency table and a message, implement an encoder and decoder. Example Follow-ups Floating-point precision limits the message length. How does integer arithmetic coding solve this? How does arithmetic coding compare to Huffman coding in compression ratio? How do you handle symbols not seen in the frequency table (zero-probability problem)?

Full Details

🔒

Unlock all Jane Street questions

Full insider details, leaked discussions, and candidate experiences.

Get full access — $100 a year, unlimited access

About This Question

This is a candidate experience report from a jane street interview during the phone round.

It covers the following topics: Coding, Onsite, Phone .

Topics

Coding Onsite Phone

Arithmetic Encoding: Implement Arithmetic Coding for Lossless Data Compression

Interview Experience

Full Details

About This Question

Topics

More Jane Street Interview Questions