How should I practice Hybrid Run-Length and Bit-Packing Encoder?

Start by reading the full statement, solve the visible examples, then compare the pattern against related Databricks onsite interview problems in FastPrep.

Is Hybrid Run-Length and Bit-Packing Encoder associated with Databricks?

FastPrep tags this as a Databricks onsite interview coding practice problem when the problem catalog has that company and stage context.

Problem · Array

Hybrid Run-Length and Bit-Packing Encoder

Learn this problem

● Hard

DatabricksFULLTIMEONSITE INTERVIEW

Problem statement

Implement encodeHybridStream, which encodes the finite integer stream values using a fixed bitWidth.

Process values in arrival order and apply these rules:

Every maximal run of at least 8 equal values becomes one run-length block.
Values that do not belong to such a run form bit-packed segments. Split each segment from left to right into groups of 8; only the final group before a run-length block or the end of the stream may contain fewer values.
Represent each value in a bit-packed group using exactly bitWidth binary digits, most significant bit first, padding with leading zeroes. Concatenate the representations in input order.
Serialize a run-length block as RLE:<value>:<count>.
Serialize a bit-packed block as BP:<count>:<bits>, where count is the number of values in that block.

The stream becomes final immediately after the last array element. Return every completed block in emission order; no later value may revise a returned block.

Function

encodeHybridStream(values: int[], bitWidth: int) → String[]

Examples

Example 1

values = [3,3,3,3,3,3,3,3,1,2,3]bitWidth = 2return = ["RLE:3:8","BP:3:011011"]

The eight leading 3s form one run-length block. The remaining values use two bits each: 1 -> 01, 2 -> 10, and 3 -> 11.

Example 2

values = [1,2,1,2,1,2,1,2,3,3,3,3,3,3,3,3,0]bitWidth = 2return = ["BP:8:0110011001100110","RLE:3:8","BP:1:00"]

The alternating prefix fills one eight-value bit-packed block. The eight 3s form a run-length block, and the final 0 is flushed as a one-value bit-packed block at the end of the stream.

Example 3

values = [5,5,5,5,5,5,5]bitWidth = 3return = ["BP:7:101101101101101101101"]

A run of seven values is below the run-length threshold, so all seven values are encoded in the final bit-packed block.

Constraints

1 <= values.length <= 100000.
1 <= bitWidth <= 16.
0 <= values[i] < 2^bitWidth.
The returned block strings must use the exact formats defined in the statement.