Databricks Coding Interview: Column Value Packer

The interviewer opens

Hi, and thanks for joining. Welcome to your interview for the software engineer role at Databricks. We'll work through one coding problem together, so please think out loud as you code, and you can pause any time with the Pause button at the top right of your screen.

The problem is about packing small integers tightly into bytes, the kind of thing a columnar storage writer does. It's in the Problem tab on the right, so please read it through, take your time, and ask me any questions before you start.

The problem

A columnar storage writer packs small integers tightly into bytes.

• values: list of non-negative integers, each less than 2^width.
• width: bits used per value (1 to 32).

Write value i into bits i*width through (i+1)*width-1 of a bit stream, least significant bit first. Stream bit k is bit (k mod 8) of byte k div 8, where bit 0 is a byte's least significant bit. Return the bytes as integers 0-255: exactly ceil(len(values)*width/8) of them, with unused high bits of the last byte set to 0.

Example: values = [1, 2, 3], width = 2 → [57]

Up to 10^5 values.