RLE And Bit-Packing Compression
Asked of: Software Engineer
Last updated

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_rleanddecode_rleareO(n)time with small state. -
Streaming RLE keeps
current_value,run_count, andpending_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 areO(n). -
Signed integer handling requires preserving two’s-complement representation; mask with
0xFFFFFFFFbefore 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 andO(1)toO(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.
Featured in interview prep guides
Practice questions
Related concepts
- Binary Serialization And CodecsCoding & Algorithms
- Serialization, Binary Encoding, And Persistent KV StoresCoding & Algorithms
- Streaming, Large Inputs, And External MemorySoftware Engineering Fundamentals
- Deterministic Tree Encoding And DecodingCoding & Algorithms
- Coding, Data Structures, And Parsing
- LRU Cache And O(1) Data StructuresCoding & Algorithms