← Databricks Interview Insights

Databricks·Software Engineer·Technical Phone Screen·Senior

SeniorPrefer not to say
May 2026Remote

Summary

Databricks coding round focused on a compression problem that combined two encoding schemes. The encoding direction was the real puzzle, and I spent most of my time second-guessing the decision logic for which scheme to apply.

Questions Asked (1)

Q1

Implement a compress and decompress function that applies Run-Length Encoding when there are at least 8 consecutive repeated values, and Bit-Packing when exactly 8 values can be packed together. The order of values must be preserved, and you have to decide on the fly which scheme to apply to each segment.

Algorithms & Data StructuresTechnical Trade-offsSystem Design
Author's notes

The decompression part is almost mechanical once you understand the format your encoder produces.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Clarify the encoding format and edge cases, then design a greedy left-to-right algorithm that at each position checks for runs of at least 8 identical values (RLE) or groups of exactly 8 distinct values (bit-packing). Implement the encoder to emit tagged segments and the decoder to reverse them, ensuring round-trip correctness and discussing trade-offs.

Pro tip: Explicitly define the output format (e.g., a byte stream with a tag byte per segment) and walk through a concrete example to demonstrate correctness and handle ambiguous cases like overlapping runs and packs.

1. Clarify requirements and format

Ask about input/output types, value range, and encoding format. Propose a simple tagged format (e.g., 0x01 for RLE, 0x02 for bit-pack) to make decoding unambiguous.

2. Design greedy encoding algorithm

Scan left to right; at each position, first check if a run of at least 8 identical values exists. If so, emit an RLE segment; otherwise, collect up to 8 distinct values and emit a bit-packed segment if exactly 8 are available.

3. Implement decoder

Read the tag byte, then decode the corresponding segment: for RLE, read the value and count; for bit-pack, read the packed bytes and unpack into 8 values. Append to output.

4. Handle edge cases and validate

Consider runs longer than 8, fewer than 8 values at the end, and values that could be either RLE or bit-packed. Ensure round-trip correctness with tests.

5. Discuss trade-offs and optimizations

Talk about time/space complexity, alternative encoding schemes, and potential improvements like using a single pass or handling larger runs more efficiently.

Key Points to Mention

  • Greedy left-to-right scanning ensures order preservation and on-the-fly decision making.
  • Tagged segment format (e.g., type byte + payload) makes decoding unambiguous.
  • RLE is chosen only for runs of at least 8 identical values; bit-packing only for exactly 8 values.
  • Edge cases: runs longer than 8, trailing values fewer than 8, and values that could be encoded either way.
  • Round-trip testing (compress then decompress yields original) is essential.
  • Time complexity is O(n) for both encoding and decoding; space complexity depends on compression ratio.

AI-generated suggestions, not part of the candidate's original notes. May be inaccurate — verify before relying on them.