How should I practice Integer Compression Offset?

Start by reading the full statement, solve the visible examples, then compare the pattern against related Headlands Technologies phone screen problems in FastPrep.

Is Integer Compression Offset associated with Headlands Technologies?

FastPrep tags this as a Headlands Technologies phone screen coding practice problem when the problem catalog has that company and stage context.

Integer Compression Offset

Headlands Technologies● MediumNEW GRADPHONE SCREEN

Problem statement

Source note: The interviewer asked for integer compression: "Most of the data is concentrated, with a few outliers. You need to find a suitable offset from the data to reduce storage space." The candidate used a sliding window to find a range covering more of the data, then set the offset. They called it a practical implementation task with an algorithmic part for choosing the offset, and they were also asked to write edge cases.

The report gives no storage format, input format or tie rule. Here, you get a bit width, each covered value takes that many bits, each outlier takes 32 bits, and the offset and any outlier markers are not counted. The offset must be one of the values, and the smallest best offset wins. You return the offset and the total bits instead of writing a full encoder. The size limits are practice choices.

The judged task matches the report at about 60%.

You need to store a list of integers, values. Most of them are close together, and a few are outliers. To save space, you pick one integer offset and store nearby values as small differences from it.

Given a bit width width, each value is stored in one of two ways:

Covered: if offset <= value <= offset + 2^width - 1, the value takes width bits.
Outlier: any other value takes 32 bits.

The offset must be one of the numbers in values. Choose the offset that gives the fewest total bits. If several offsets give the same total, choose the smallest one.

Return an array [offset, totalBits]. Count every value, including duplicates. Ignore the space needed to store the offset itself or to mark which values are outliers.

In the interview, the candidate also had to write edge cases, so try writing your own before you run the code.

Function

chooseCompressionOffset(values: int[], width: int) → int[]

Examples

Example 1

values = [100,102,101,105,3000,103]width = 3return = [100,47]

With width = 3, an offset covers 8 values in a row. The offset 100 covers 100 through 107, which holds 5 values. The value 3000 is an outlier. The total is 5 * 3 + 1 * 32 = 47 bits.

Example 2

values = [10,-5,11,-4]width = 1return = [-5,66]

With width = 1, an offset covers 2 values in a row. The offsets -5 and 10 each cover 2 values, so the tie goes to the smaller offset, -5. The total is 2 * 1 + 2 * 32 = 66 bits.

Example 3

values = [0,255,256]width = 8return = [0,48]

With width = 8, the offset 0 covers 0 through 255, so 256 is just outside. The offset 255 also covers 2 values, so the tie goes to 0. The total is 2 * 8 + 1 * 32 = 48 bits.

Constraints

1 <= values.length <= 5000
-2^31 <= values[i] <= 2^31 - 1
1 <= width <= 31