RLE And Bit-Packing Compression

What's being tested

Tests lossless compression implementation with careful state management, bit manipulation, and edge-case handling. Strong answers show clean encoder/decoder symmetry, correct handling of 32-bit signed integers, and streaming-safe APIs that do not require loading all input into memory.

Patterns & templates

• Run-length encoding groups consecutive equal values as (value, count); encode_rle and decode_rle are O(n) time with small state.

• Streaming RLE keeps current_value, run_count, and pending_output; flush on value change, count limit, or end-of-stream.

• Bit packing stores fixed-width integers using bit_buffer, bits_in_buffer, and masks like (1 << width) - 1; encode/decode are O(n).

• Signed integer handling requires preserving two’s-complement representation; mask with 0xFFFFFFFF before packing and reinterpret on decode.

• Header design separates metadata from payload: store mode, bit width, run length, or block size so decoder can unambiguously parse bytes.

• Decoder symmetry matters: every encoder write path needs a corresponding read path; test round-trips with decode(encode(x)) == x.

• Complexity target is O(n) time and O(1) to O(block_size) auxiliary space; avoid string concatenation or per-bit arrays for large inputs.

Common pitfalls

Pitfall: Forgetting to flush the final RLE run produces correct output for mid-stream transitions but loses the last value.

Pitfall: Using arithmetic right shift or signed casts inconsistently can corrupt negative numbers during bit-packing decode.

Pitfall: Designing an ambiguous format, such as writing counts and values without delimiters, widths, or block metadata, makes decoding impossible.

Practice these

The practice cards below cover the canonical variants — solve all of them and time yourself.