Build a compression encoder: A Sample Coding Interview Solution

The coding question

Write an encoder and decoder for a list of integers. Use run-length encoding for repeated values and bit packing for the rest, and make sure decoding gives back exactly the original list.

Ask a few questions first

Ask	What we'll assume
What range are the integers in?	Signed, and they fit in 64 bits. Negatives are allowed.
What should encode return?	Bytes. Decode takes those bytes and returns the list.
Do I get to design the format?	Yes. Explain it before you code it.
What counts as a run?	Your call. We'll say 4 or more of the same value in a row. Shorter runs are cheaper to pack.
What about bad input to decode?	Raise an error rather than return garbage.

A couple of examples

Input	Output
[7, 7, 7, 7, 7, 7, 1, 2, 3]	8 bytes: 00 06 0e 01 03 03 a2 01, which decodes back to the same list
[-1, 5, -1, 5]	5 bytes: 01 04 04 a1 a1
[]	0 bytes, which decodes to []

Start with brute force

Write every number as a fixed 8 bytes. It's trivially correct and makes a good baseline to compare against, but it doesn't compress anything.

Cost: O(n) time and always 8n bytes. A run of a million zeros takes 8 MB.

A better way

This one is about getting the format exactly right, so design it out loud before writing code. The output is a list of blocks. Each block starts with a type byte and a count. A run block then holds one value. A packed block holds a bit width and then every value squeezed into that many bits.

Two small tricks keep it compact. Varints store a number in 7 bits per byte, with the top bit saying whether more bytes follow, so small counts take one byte. Zigzag maps 0, -1, 1, -2, 2 to 0, 1, 2, 3, 4, so small negative numbers don't need all 64 bits.

The encoder walks the list once. When it finds a run that's long enough, it writes any waiting literals as a packed block, then writes the run. Everything else collects into the literal buffer.

Walk the list and find the next run of equal values.
If the run is at least 4 long, flush any waiting literals as a packed block, then write a run block: type 0, count, zigzag value.
Otherwise add the run's values to the literal buffer.
A packed block is type 1, the count, the bit width of the biggest zigzag value, then the values packed low bits first.
Decode reads a type byte and a count, then either repeats the value or unpacks count values of the given width.

The code

solution.pypython

RUN, PACKED = 0, 1
MIN_RUN = 4  # shorter runs are cheaper to pack than to describe


def zigzag(n):
    # 0, -1, 1, -2, 2 ... -> 0, 1, 2, 3, 4, so small negatives stay small
    return n * 2 if n >= 0 else -n * 2 - 1


def unzigzag(z):
    return z // 2 if z % 2 == 0 else -(z + 1) // 2


def write_varint(out, n):
    # 7 bits per byte, high bit set means "more bytes follow"
    while n >= 0x80:
        out.append((n & 0x7F) | 0x80)
        n >>= 7
    out.append(n)


def read_varint(data, pos):
    n = shift = 0
    while True:
        if pos >= len(data):
            raise ValueError("truncated input")
        byte = data[pos]
        pos += 1
        n |= (byte & 0x7F) << shift
        shift += 7
        if byte < 0x80:
            return n, pos


def write_packed(out, values):
    zs = [zigzag(v) for v in values]
    width = max(zs).bit_length()  # bits needed for the biggest value
    out.append(PACKED)
    write_varint(out, len(zs))
    out.append(width)
    acc = bits = 0
    for z in zs:
        acc |= z << bits
        bits += width
        while bits >= 8:
            out.append(acc & 0xFF)
            acc >>= 8
            bits -= 8
    if bits:
        out.append(acc)  # last partial byte, padded with zeros


def encode(values):
    out = bytearray()
    literals = []
    i = 0
    while i < len(values):
        j = i
        while j < len(values) and values[j] == values[i]:
            j += 1
        if j - i >= MIN_RUN:
            if literals:
                write_packed(out, literals)
                literals = []
            out.append(RUN)
            write_varint(out, j - i)
            write_varint(out, zigzag(values[i]))
        else:
            literals.extend(values[i:j])
        i = j
    if literals:
        write_packed(out, literals)
    return bytes(out)


def decode(data):
    values = []
    pos = 0
    while pos < len(data):
        kind = data[pos]
        pos += 1
        count, pos = read_varint(data, pos)
        if kind == RUN:
            z, pos = read_varint(data, pos)
            values.extend([unzigzag(z)] * count)
        elif kind == PACKED:
            width = data[pos]
            pos += 1
            nbytes = (count * width + 7) // 8
            if pos + nbytes > len(data):
                raise ValueError("truncated input")
            chunk = int.from_bytes(data[pos:pos + nbytes], "little")
            mask = (1 << width) - 1
            for k in range(count):
                values.append(unzigzag((chunk >> (k * width)) & mask))
            pos += nbytes
        else:
            raise ValueError("unknown block type")
    return values

	Cost	Why
Encode time	O(n)	One pass to find runs, and each value is packed once
Decode time	O(n)	Each block is read once (the big-integer shift is fine at interview sizes)
Output size	Depends on the data	A run costs about 3 bytes however long it is. Literals cost their bit width each, plus a couple of header bytes per block

Test it

Walk through one of the examples out loud, then check the cases that tend to break things:

An empty list encodes to empty bytes and decodes back to [].
All zeros that aren't a run, like [0, 0, 0], give a bit width of 0. Make sure decode handles that.
The smallest and biggest 64-bit values, which need the full width after zigzag.
A run of exactly 3 vs exactly 4, right on the boundary.
Runs longer than 127, so the count needs a multi-byte varint.
Truncated or corrupted bytes, which should raise an error.

Common mistakes

Forgetting to flush the literal buffer at the end, so the last few values vanish.
Packing negative numbers directly. Their bit length looks small in Python but they don't round-trip.
Not storing the count in a packed block, so the decoder can't tell padding bits from a real 0.
Testing only the happy examples. Write a round-trip test over random lists, with lots of repeats and negatives mixed in.

Follow-up questions

How would you make one outlier not ruin a packed block?

One huge value forces a big width on everything around it. Split literals into smaller blocks, say 128 values each, so an outlier only hurts its own block. Real formats like Parquet's do something similar.

How would you let someone read the 1,000,000th value without decoding everything?

Add a small index at the end: for every block, where it starts in the bytes and which value number it starts at. Binary search the index, then decode just that block.

What about values that are close together but not equal, like timestamps?

Store the first value, then the differences between neighbors. The differences are small, so they pack into very few bits.

How the time adds up

Minutes	What you're doing
0–5	Ask questions and agree on examples
5–10	Talk through the brute force
10–20	Find the better approach
20–35	Write the code
35–40	Test it out loud
40–45	Follow-up questions

Key concepts used here

Bit manipulationMasks, shifts and XOR, for flags, packing and IP addresses.

We wrote this sample solution ourselves. Practice Loop is independent and isn't affiliated with or endorsed by Databricks.