Summary
Databricks SWE interview threw a full codec design problem at me, streaming compression with RLE and bit-packing. More involved than I expected for a single session, felt like a take-home crammed into live coding.
Questions Asked(4)
This one took me a minute to even parse.
Suggested Approach
Start by clarifying the block-based streaming model and the decision boundary between RLE and bit-packing, then implement each encoding strategy modularly before wiring them into a unified codec with a heuristic selector. Emphasize that the design mirrors real columnar storage engines (like Parquet/Delta Lake) to show domain awareness relevant to Databricks.
Clarify Requirements & Constraints
Ask about block size (e.g., 128 or 256 values), the integer range (affects bit-width calculation), and whether the codec must be streamable/seekable. Confirm the output format: does each block carry a header indicating its encoding type?
Define the Block Structure & Decision Heuristic
Design a block header (e.g., 1-byte flag: 0x00 = RLE, 0x01 = bit-packed) followed by encoded payload. Establish the selection heuristic: use RLE when a run of repeated values exceeds a threshold (e.g., run length > 8), otherwise default to bit-packing.
Implement RLE Encoding
Buffer incoming values, detect runs of identical integers, and emit (count, value) pairs. Handle the edge case where a run spans a block boundary by flushing the current block and starting a new one.
Implement Bit-Packed Encoding
Compute the minimum bit-width needed to represent all values in the current block (ceil(log2(max_value + 1))), store the bit-width in the block header, then pack values tightly using bitwise operations into a byte array.
Integrate, Test & Discuss Trade-offs
Wire both strategies into a streaming encoder that buffers a full block, applies the heuristic, and flushes encoded bytes. Discuss trade-offs: RLE excels on low-cardinality sorted data; bit-packing wins for random distributions; a hybrid (like Parquet's RLE/bit-packing) handles both.
Key Points to Mention
Spent more time here than I should have.
Suggested Approach
Start by clearly distinguishing the two encoding types at a structural level, then walk through each block's memory layout field by field with precise byte sizes and ordering. Ground your explanation in the Apache Parquet RLE/Bit-Packing Hybrid encoding spec, since that is the canonical reference Databricks engineers work with daily.
Establish the Hybrid Encoding Context
Briefly explain that Parquet uses a single RLE/Bit-Packing Hybrid stream where a 1-byte header per group encodes both the encoding type (LSB = 1 for bit-packed, LSB = 0 for RLE) and the group length, so decoders know which structure to parse next.
Define the RLE Block Structure
Describe the RLE block as: a variable-length integer (VarInt) header encoding (run_length << 1 | 0), followed by the repeated value stored in ceil(bit_width / 8) bytes, little-endian. Emphasize that the bit-width used here is the same global or per-page bit-width negotiated upfront.
Define the Bit-Packed Block Structure
Describe the bit-packed block as: a VarInt header encoding ((num_groups << 1) | 1), followed by a tightly packed byte array where values are written LSB-first, with groups of 8 values packed into exactly bit_width bytes, and the final group zero-padded to a full byte boundary.
Explain Bit-Width Determination
Clarify that bit-width is computed per page (or per block in some implementations) as ceil(log2(max_value + 1)), capped at 32 bits, and written once into the page/column-chunk header so all blocks in that scope share it — avoiding per-block overhead while still adapting to data range.
Address Trade-offs and Edge Cases
Discuss edge cases such as bit_width = 0 (all values are zero, payload is empty), alignment padding in the bit-packed payload, and why groups of 8 values are chosen — it ensures the packed group always occupies a whole number of bytes (8 values × bit_width bits = bit_width bytes), simplifying decoding.
Key Points to Mention
Decoder felt more straightforward once the block format was locked in.
Suggested Approach
Design the Decoder as a Python iterator class implementing __iter__ and __next__, which processes a list of encoded blocks sequentially and dispatches to RLE or bit-packed decoding logic based on a block type header. Maintain internal state (current block index and position within the block) to yield one integer at a time, ensuring lazy evaluation and memory efficiency. Clarify the encoding format upfront before coding to avoid mismatched assumptions.
Clarify the Encoding Format
Ask about the block structure: how the block type is indicated (e.g., a header byte or flag), the RLE format (count + value), and the bit-packing format (bit-width + packed bytes). Confirm the integer range and whether blocks are byte-aligned.
Design the Iterator Interface
Define a Decoder class with __init__ accepting the encoded block list, and implement __iter__ (returning self) and __next__ (raising StopIteration when exhausted). Sketch out the internal state variables: current block index, a buffer or generator for the active block's values, and position tracking.
Implement Block Dispatching
In __next__, if the internal buffer is empty, advance to the next block and inspect its type header to call either decode_rle_block or decode_bitpacked_block, storing results in a local iterator or deque. Yield values from the buffer one at a time.
Implement RLE and Bit-Pack Decoders
For RLE, extract the repeat count and literal value, then yield the value 'count' times. For bit-packing, read the bit-width, unpack the bytes using bitwise operations or Python's int.from_bytes, and yield each extracted integer.
Test Edge Cases and Validate
Test with an empty block list, a single-element RLE block, maximum bit-width values, and mixed block sequences. Verify the reconstructed sequence matches the original and discuss time complexity (O(n) total) and memory efficiency (O(block_size) at most).
Key Points to Mention
Ran out of time here.
Suggested Approach
Structure your unit tests around distinct behavioral categories: boundary conditions, typical use cases, and stress patterns like long runs or alternating encodings. For each test case, clearly document the intent, construct a precise input, and assert both the encoded output and the ability to decode back to the original sequence. Treat this as a specification exercise — your tests should serve as living documentation of the encoding contract.
Identify Test Categories
Map out the five required test categories from the prompt: no-repeats, long single-value runs, alternating RLE/bit-packed patterns, edge integer values, and empty input. Briefly explain why each category targets a distinct code path or failure mode.
Design Inputs and Expected Outputs
For each category, construct a concrete input array and derive the expected encoded output by hand or by reasoning through the algorithm. Ensure expected outputs reflect both the encoding scheme and any header/metadata your implementation produces.
Write Assertions for Encoding and Round-Trip
Assert that the encoder produces the exact expected byte/int sequence, and add a round-trip assertion that decode(encode(input)) equals the original input. This dual assertion catches both over-encoding and lossy compression bugs.
Handle Edge and Boundary Values
Write dedicated tests for Integer.MAX_VALUE, Integer.MIN_VALUE, and the empty array, verifying that no overflow, sign-extension, or null-pointer issues occur. Check that the empty case returns an empty or well-defined sentinel output rather than throwing.
Validate Alternating Pattern Transitions
Construct a sequence that forces the encoder to switch between RLE and bit-packed modes multiple times (e.g., [1,1,1,2,3,4,5,5,5]) and assert that mode boundaries are encoded correctly. This stress-tests the state machine logic that decides which encoding to apply.
Key Points to Mention
Discussion(3)
Sign in to join the discussion.
Empty input first, always. It's two lines and it catches null pointer bugs you didn't know you had.
The streaming constraint is what makes this problem actually hard, and I think a lot of people underestimate it until they're mid-implementation and realize they've implicitly assumed lookahead somewhere. The mental model that helped me on a similar problem was thinking of the encoder as a small state machine with two states: accumulating a run, or accumulating a bit-pack block. You buffer incoming values and track the current run length alongside the block buffer. When a run breaks (next value differs from the current run value), you have to decide: was the run long enough to justify flushing it as an RLE block? A common heuristic is something like, if run length times the cost of a raw value is greater than the fixed RLE block overhead, flush RLE, otherwise absorb those repeated values into the bit-pack buffer and continue.
The transition edge case you mentioned is the real gotcha. My take: leftover non-RLE values before a run starts should stay in the current BP block if there's room, and the run itself starts a fresh RLE block only when it actually terminates (or the stream ends). The opposite direction, a run ending mid-stream, means you flush the RLE block and any new values start accumulating in a fresh BP block. Trying to merge them into one block type is where the logic gets tangled. Keep the flush paths clean and separate and the transitions become much easier to reason about.
One concrete thing: define a flushCurrentBlock() helper early and call it from every transition point. That single function handles the 'which type do I emit' decision based on current state, and it keeps your add(int value) method readable.
Iterator state across block boundaries is genuinely the only interesting part here. Keep a block index and a position-within-block index, and your hasNext() just checks whether you've exhausted both. For RLE blocks you track how many of the repeated value you've already emitted. For BP blocks you track the bit offset into the payload byte array.
The bit extraction for BP is a few lines but worth getting right: given bit offset o and width w, you compute which byte(s) to read, mask and shift. Something like reading a 32-bit window from the byte array at byte offset o/8, then right-shifting by (o%8) and masking with (1<<w)-1, handling the sign extension if your values are signed. Skipping error handling for malformed blocks is understandable under time pressure but worth mentioning to the interviewer proactively, something like 'in production I'd validate block type byte and throw a specific exception rather than silently misbehaving.' That acknowledgment usually lands better than them having to flag it.