Coding - Integer Stream Encoder/Decoder

A core difficulty is that any partial run could potentially be "the last run" until you're told to finalize.

Problem Statement

Design and implement a streaming compression system for 32-bit integers that intelligently selects between two encoding schemes to minimize space. The system must process integers in a streaming fashion without buffering the entire input, handling two compression methods: Run-Length Encoding for repeated values and Bit-Packing for non-repeating sequences.

This problem combines algorithm design with practical streaming constraints. You'll need to make real-time decisions about encoding without knowing future values, handle the ambiguity of partial runs, and optimize for both memory efficiency and correctness.

Key Requirements

Functional

• Streaming encoder -- process integers one at a time via append(value) without storing the entire input

• Dual encoding schemes -- support both Run-Length Encoding (RLE) for repeated values and Bit-Packing (BP) for diverse values

• Intelligent scheme selection -- choose RLE when 8+ consecutive identical values exist, otherwise use BP for exactly 8 values

• Last run flexibility -- allow runs with fewer than 8 values only for the final run in the stream

• Decoder implementation -- decompress encoded runs back to the original integer sequence

Non-Functional

• Minimal buffering -- encoder should maintain minimal internal state, not buffer thousands of values

• Correctness guarantees -- must preserve exact order and values when encoding then decoding

• Space efficiency -- RLE should achieve extreme compression for repeated values (9 integers → 2 numbers)

• Real-time decisions -- make encoding choices incrementally without lookahead beyond buffering requirements

• Unambiguous output -- encoded format must clearly distinguish between RLE and BP runs

Based on real interview experiences, these are the areas interviewers probe most deeply:

1. Understanding the Streaming Constraint (Most Emphasized)

The critical challenge is that you cannot see all values upfront. Interviewers want to see how you handle the fundamental tension: you must decide whether to emit a run now or wait for more values.

• Maintain a small buffer of pending values that haven't been committed to any run yet

• Emit an RLE run immediately when you detect 8+ consecutive identical values

• Emit a BP run when your buffer reaches 8+ values that cannot form RLE

• On finish(), flush any remaining buffered values as the final run

• Handle the case where you have 5 identical values buffered -- could become RLE if more arrive, or BP if stream ends

Interviewers probe whether you understand all the encoding rules and their interactions, especially the exceptions.

• RLE minimum is 8 values EXCEPT for the last run, which can be smaller

• BP runs must be exactly 8 values EXCEPT for the last run, which can be smaller

• RLE is preferred over BP when both are applicable (for compression efficiency)

• Once an RLE run starts, extend it as far as possible -- don't stop at 8 if value keeps repeating

• Order must be preserved -- you cannot reorder values to create better compression

• Buffer of 5 identical values: wait for more (could reach 8), or emit as last run if stream ends

• Buffer of 7 diverse values: need 1 more for BP, but if stream ends, emit as last BP run

• The finish() method is your signal that no more values are coming -- flush everything remaining

• Consider whether to prefer RLE or BP for small final runs with repeated values (RLE is more efficient)

Interviewers will test your solution on tricky inputs to verify you handle all scenarios.

• Empty stream: should return empty list of runs

• Stream of 1-7 values (all identical): emit single RLE run as last run

• Stream of 1-7 values (all different): emit single BP run as last run

• Exactly 8 values all identical: emit RLE[value, 8]

• Exactly 8 values all different: emit BP with 8 values

• Interleaved patterns like [8 identical] + [4 different]: RLE[8] + BP[4] as last run

• Very long repeated sequence (millions of same value): single RLE run with large count

After implementing basic streaming, interviewers often ask about optimization.