0

Hybrid run-length and bit-packing codec

by Frontier Interview· 1 day ago· ⑂ 0 remixes

Question: Hybrid run-length and bit-packing codec

Companies: Databricks

Difficulty: Medium

Problem statement

Design an encoder and a decoder for a list of non-negative integers. The encoder compresses the list into a list of human-readable run strings. The decoder restores the original list exactly.

There are two kinds of run:

  • Run-length run: "RLE[value, count]" means value repeated count times (count >= 1).
  • Bit-packed run: "BP[width, v1, v2, ...]" stores one or more literal values. width is the number of bits needed for the largest value in the run (at least 1, so a run of zeros has width 1). Every value must fit in width bits.

Implement:

  • encode(nums: List[int], min_run: int = 3) -> List[str]: scan the input as maximal runs of equal values. A run at least min_run long becomes an RLE run. Shorter runs are collected, in order, into a single BP run that ends just before the next RLE run or at the end of the input.
  • decode(runs: List[str]) -> List[int]: concatenate the runs. Raise ValueError on malformed input (unknown prefix, count <= 0, an empty BP run, or a value wider than its declared width).

decode(encode(nums)) == nums must hold for every valid input.

Constraints

  • 0 <= len(nums) <= 10^5
  • 0 <= nums[i] < 2^31
  • Both operations should run in linear time.

Example 1

nums   = [4, 4, 4, 4, 6, 1, 2, 2, 8, 8, 8]
encode -> ["RLE[4, 4]", "BP[3, 6, 1, 2, 2]", "RLE[8, 3]"]

The runs of 4 and 8 are long enough for RLE. The values 6, 1, 2, 2 are packed together. The largest of them is 6, which needs 3 bits.

Example 2

runs   = ["BP[1, 0, 1]", "RLE[3, 2]"]
decode -> [0, 1, 3, 3]

Be ready for follow-ups: write the runs as real packed bits, choose the split by encoded size instead of a fixed threshold, stream values in and out with bounded memory, and support signed 32-bit integers.

Reconstructed from the reported question; details may differ from what interviewers ask.

Approach

The input is a list of non-negative integers. The output is a list of run strings in input order. There are two kinds of run:

  • RLE[value, count]: value repeated count times.
  • BP[width, v1, v2, ...]: literal values stored at width bits each, where width is the bit length of the largest value in the run (at least 1).

Decoding concatenates the runs, so decode(encode(a)) == a must hold for every input.

Brute force. Emit one BP run per value, or one RLE run per maximal group of equal values. Both round-trip, but neither one compresses. A long run costs count slots as BP, and a noisy stretch costs a whole run string per value as RLE. Say this out loud, then fix the rule that decides between them.

Greedy split. Walk the array once and cut it into maximal runs of equal values. For each run:

  • If its length is at least min_run (3 by default), flush any pending literals as one BP run, then emit RLE[value, length].
  • Otherwise, append its values to the pending literal buffer.

At the end, flush the buffer. Short runs cost less as literals, because an RLE header spends two numbers on what might be only one or two values. Long runs cost less as RLE, because the cost no longer grows with the length.

Invariants.

  • Every input index lands in exactly one output run, and the runs come out in input order. We flush before each RLE run and once at the end, so no literal is reordered or dropped.
  • A BP run never has an empty value list, and its width fits every value in it.
  • An RLE run always has count >= min_run >= 1.

The decoder validates the same rules (a known prefix, a positive count, values that fit the width), so it rejects corrupt input instead of returning a wrong array.

Code

import re
from typing import List

MIN_RUN = 3  # runs at least this long become RLE


def bit_width(values: List[int]) -> int:
    """Bits needed for the largest value; at least 1 so zeros still take a slot."""
    return max(1, max(values).bit_length())


def encode(nums: List[int], min_run: int = MIN_RUN) -> List[str]:
    if any(v < 0 for v in nums):
        raise ValueError("values must be non-negative")
    out: List[str] = []
    pending: List[int] = []              # literals waiting for a BP run

    def flush() -> None:
        if pending:
            w = bit_width(pending)
            out.append(f"BP[{w}, " + ", ".join(map(str, pending)) + "]")
            pending.clear()

    i, n = 0, len(nums)
    while i < n:
        j = i
        while j < n and nums[j] == nums[i]:
            j += 1                       # nums[i:j] is one maximal run
        if j - i >= min_run:
            flush()                      # keep output order = input order
            out.append(f"RLE[{nums[i]}, {j - i}]")
        else:
            pending.extend(nums[i:j])
        i = j
    flush()
    return out


_RUN = re.compile(r"^(RLE|BP)\[(.*)\]$")


def decode(runs: List[str]) -> List[int]:
    result: List[int] = []
    for run in runs:
        m = _RUN.match(run.strip())
        if not m:
            raise ValueError(f"bad run: {run!r}")
        kind = m.group(1)
        fields = [int(x) for x in m.group(2).split(",")]
        if kind == "RLE":
            if len(fields) != 2 or fields[1] <= 0:
                raise ValueError(f"bad RLE run: {run!r}")
            value, count = fields
            result.extend([value] * count)
        else:
            width, values = fields[0], fields[1:]
            if not values:
                raise ValueError(f"empty BP run: {run!r}")
            if any(v < 0 or v.bit_length() > width for v in values):
                raise ValueError(f"value wider than {width} bits: {run!r}")
            result.extend(values)
    return result


if __name__ == "__main__":
    data = [5, 5, 5, 5, 1, 2, 3, 0, 0, 0]
    runs = encode(data)
    assert runs == ["RLE[5, 4]", "BP[2, 1, 2, 3]", "RLE[0, 3]"]
    assert decode(runs) == data
    assert encode([]) == [] and decode([]) == []

Complexity

  • encode: O(n) time. Each index is visited once by the run scan and once when it is copied to the buffer or counted. Output size is O(n) in the worst case (all literals). Extra space is the pending buffer, O(n).
  • decode: O(n + total output length) time, where the output length is the sum of all RLE counts plus the BP values. Parsing is linear in the total string length. Space is the output array.
  • bit_width: O(k) for a run of k values.

Test cases

  • [] -> [], and decode([]) -> [].
  • [0] -> ["BP[1, 0]"] (zero still takes one bit).
  • [9, 9, 9] -> ["RLE[9, 3]"] (exactly min_run).
  • [7, 7, 2] -> ["BP[3, 7, 7, 2]"] (a run of 2 is too short for RLE).
  • [5, 5, 5, 5, 1, 2, 3, 0, 0, 0] -> ["RLE[5, 4]", "BP[2, 1, 2, 3]", "RLE[0, 3]"].
  • [1, 1, 4, 4, 4, 4, 4, 1, 1] -> ["BP[1, 1, 1]", "RLE[4, 5]", "BP[1, 1, 1]"] (literals on both sides are flushed in order).
  • [1023, 1] -> ["BP[10, 1023, 1]"] (width comes from the largest value).
  • decode(["RLE[2, 3]", "BP[4, 9, 15]"]) -> [2, 2, 2, 9, 15].
  • decode(["BP[2, 4]"]) raises: 4 needs 3 bits. decode(["RLE[1, 0]"]) raises. An unknown prefix raises.
  • Randomized round-trip: for random arrays with values from a small set, decode(encode(a)) == a with min_run set to 1 and to 3.
  • Negative input to encode raises ValueError.

Follow-ups

  1. Encode to real bits, not strings. Write a BitWriter that appends width bits per BP value and pads each BP group to a byte boundary. Store a header per run, for example a varint (count << 1) | is_rle, followed by either the value in ceil(width / 8) bytes or the packed literals. This is the Parquet RLE/bit-packing hybrid. A common choice is one fixed width for the whole column, with BP groups padded to a multiple of 8 values so each group ends on a byte. The decoder reads the header, then shifts and masks.
  2. Pick runs by cost, not by a fixed threshold. Give each run a size in bits: RLE costs a fixed header plus the value, and BP costs a header plus k * width. Then choose the split with a DP over run boundaries: best[i] = min(best[j] + cost(j, i)). Restrict j to run boundaries and cap BP group length to keep it near linear. The DP shows when merging a short run into a neighboring BP group is cheaper, or when a wide outlier should split a BP group so that its large width does not apply to the whole group.
  3. Streaming. Turn the encoder into a class with push(value) and finish(). Keep the current run (value, length) and the pending literal buffer. When the run breaks, decide RLE or literal as before. Cap the buffer (for example at 512 values) and flush a BP run when it is full, so memory stays bounded. The decoder becomes a generator that yields values run by run without building the whole array.
  4. Negative numbers and 32-bit limits. Zigzag-encode signed values ((v << 1) ^ (v >> 31), then mask to 32 bits) before computing widths, and decode with (u >> 1) ^ -(u & 1). A naive bit_length on negatives or an arithmetic shift where a logical one is needed is the usual bug here.
  5. Random access. To support get(i) without decoding everything, store the cumulative start index of each run and binary-search it. Inside a bit-packed run, value k is at bit offset k * width.

Interviewer expectations

Mid-level (L4)

  • Pins down both formats and the round-trip requirement before coding.
  • Writes a correct single-pass encoder and remembers to flush the trailing literal buffer.
  • Writes a decoder that parses both run types and tests empty input, a single value, and a run of exactly min_run.

Senior (L5)

  • Explains why short runs go to BP and long runs go to RLE, and picks the threshold on purpose.
  • Validates input in the decoder (bad prefix, zero count, value wider than the width) instead of trusting it.
  • Moves to a streaming encoder/decoder with a bounded buffer, and handles signed values with zigzag encoding.

Staff (L6+)

  • Connects the problem to columnar formats (Parquet, Delta): fixed column width, 8-value groups, byte alignment, and why decoding speed matters as much as size.
  • Formulates the cost-based split as a DP and discusses the trade-off between its compression gain and its encode cost.
  • Discusses random access, dictionary encoding before RLE/BP, and how to version the format so old files still decode.

Sign in to comment, vote or remix.