Quick Overview

This question evaluates understanding of simple lossless compression techniques and related competencies such as string processing and parsing for run-length encoding, bit-level operations and packing for fixed-width integer compression, and algorithmic complexity analysis.

Implement RLE and bit-packing compression

Company: Databricks

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Onsite

You are asked to implement two related compression/decompression schemes: **Run-Length Encoding (RLE)** and **bit-packing**. --- ## Part 1 — Run-Length Encoding (RLE) Implement RLE compression and decompression for a string consisting of characters in the ASCII range. ### RLE compression - **Input**: a string, for example: `"AAABCCDDDD"`. - **Output**: an encoded string that replaces consecutive runs of the same character with a count followed by the character. - For example, the above input could be encoded as: `"3A1B2C4D"`. Requirements: - Implement a function/method that takes the original string and returns the compressed string. - If a character appears only once, its count should still be included (e.g., `"1B"`). - Think about edge cases, such as: - Empty string. - String with one character. - Very long runs (counts larger than 9, larger than 255, etc.). - You may assume the counts fit in a standard integer type. ### RLE decompression - Implement a function/method that takes a valid RLE-encoded string (e.g., `"3A1B2C4D"`) and reconstructs the original string (e.g., `"AAABCCDDDD"`). - You may assume the input is well-formed (digits representing a positive integer count immediately followed by a single character). Describe the time and space complexity of your compression and decompression algorithms. --- ## Part 2 — Bit-Packing Compression for Small Integers You are given an array of non-negative integers, each guaranteed to be in the range `[0, 15]` (i.e., each value fits in 4 bits). ### Bit-packing compression - **Input**: an array of integers, for example: `[3, 15, 0, 7]`. - **Output**: a byte array that packs two 4-bit values into each byte: - The first value in the pair occupies the **high 4 bits** of the byte. - The second value occupies the **low 4 bits** of the byte. - For example, for `[3, 15]`: - `3` in binary (4 bits) is `0011`. - `15` in binary (4 bits) is `1111`. - The packed byte is `00111111` (0x3F). - If the input array has an **odd** number of elements, the last byte should have the last value in the high 4 bits and the low 4 bits set to zero. Implement a function/method that: - Takes the array of integers `[0..15]` as input. - Returns a byte array representing the packed data. ### Bit-packing decompression - Implement the inverse function that takes a packed byte array and the **original number of integers** `n`, and reconstructs the original array of integers. - You may assume `n` is provided and matches the original length. Again, describe the time and space complexity of your compression and decompression algorithms. You do **not** need to provide code in a specific language for this prompt, but your explanation should be detailed enough that code could be written directly from it.

Overview: This question evaluates understanding of simple lossless compression techniques and related competencies such as string processing and parsing for run-length encoding, bit-level operations and packing for fixed-width integer compression, and algorithmic complexity analysis.

Part 1: Run-Length Encoding (RLE)

Implement a function that performs either RLE compression or RLE decompression. Use the function signature solution(mode, text): - If mode == 'compress', text is a raw string and you must replace each maximal run of identical consecutive characters with '<count><character>'. For example, 'AAABCCDDDD' becomes '3A1B2C4D'. Counts of 1 must still be written. - If mode == 'decompress', text is a valid encoded string in that same format, and you must reconstruct the original string. To keep decoding unambiguous, the raw input for compression in this problem will not contain digit characters '0' through '9'. Empty strings are allowed.

Constraints

  • mode is either 'compress' or 'decompress'.
  • For compression, 0 <= len(text) <= 100000.
  • For compression, text contains printable ASCII characters excluding digits '0'..'9'.
  • For decompression, text is well-formed as zero or more groups of <positive integer><single non-digit character>.
  • Counts fit in a standard integer type, and the fully decoded output length is at most 1000000.

Examples

Input: ('compress', 'AAABCCDDDD')

Expected Output: '3A1B2C4D'

Explanation: Runs are AAA, B, CC, and DDDD, so the encoded form is 3A1B2C4D.

Input: ('decompress', '3A1B2C4D')

Expected Output: 'AAABCCDDDD'

Explanation: Expand each count-character pair back into repeated characters.

Hints

  1. For compression, scan left to right while tracking the current character and its run length.
  2. For decompression, counts may have multiple digits, so collect consecutive digits before reading the following character.

Part 2: Bit-Packing Compression for Small Integers

Implement a function that either packs or unpacks 4-bit integers. Use the function signature solution(mode, data, n=None): - If mode == 'pack', data is a list of non-negative integers in the range [0, 15]. Pack two values into each byte: the first value goes in the high 4 bits and the second value goes in the low 4 bits. - If mode == 'unpack', data is a packed byte array represented as a list of integers in [0, 255], and n is the original number of 4-bit integers. Reconstruct and return the original list. If there is an odd number of values during packing, store the final value in the high 4 bits of the last byte and set the low 4 bits to 0. Because this platform uses Python literals, represent the byte array as a list of integers rather than a bytes object.

Constraints

  • mode is either 'pack' or 'unpack'.
  • For packing, 0 <= len(data) <= 100000 and every value is in [0, 15].
  • For unpacking, n is a non-negative integer and len(data) == ceil(n / 2).
  • For unpacking, every packed byte is in [0, 255].
  • Empty input is allowed.

Examples

Input: ('pack', [3, 15, 0, 7], None)

Expected Output: [63, 7]

Explanation: [3, 15] becomes 0x3F = 63 and [0, 7] becomes 0x07 = 7.

Input: ('unpack', [63, 7], 4)

Expected Output: [3, 15, 0, 7]

Explanation: Split each byte into its high and low 4-bit parts.

Approach

This solution implements 4-bit (nibble) packing/unpacking, branching on mode. Pack. Each byte holds two 4-bit values: the first in the high nibble, the second in the low nibble. The loop walks data in steps of 2 with index i: - first = data[i] (validated to be in [0, 15]). - second = data[i+1] if it exists, otherwise 0 — this is exactly the "odd count → pad low nibble with 0" rule. - Combine with packed.append((first << 4) | second): shifting first left by 4 bits moves it into the high nibble, and OR-ing second fills the low nibble. So [3, 15] → (3<<4)|15 = 48|15 = 63, and a trailing 5 becomes 5<<4 = 80. Unpack. Given the packed bytes and the original count n, it first checks len(data) == ceil(n/2) (written as (n+1)//2). For each byte it extracts: - the high nibble: (byte >> 4) & 0xF - the low nibble: byte & 0xF Each is appended only while len(result) < n, which transparently drops the zero-padding nibble of the last byte when n is odd. This guards every append, so no extra trailing zero leaks into the output. Why correct. Packing and unpacking are exact inverses: the <<4 | step is undone by >>4 and & 0xF, and the len(result) < n cap restores the original length. Empty input yields [] in both directions. Bounds checks ([0,15] for values, [0,255] for bytes, non-negative n) make it robust to malformed input.

Time complexity: O(n), where n is the number of 4-bit integers. Pack visits each of the n inputs once (producing ceil(n/2) bytes); unpack visits each of the ceil(n/2) bytes once and emits up to n values.

Space complexity: O(n) for the output. Pack allocates ceil(n/2) bytes; unpack allocates up to n values. Aside from the output list, only O(1) auxiliary space is used.

Hints

  1. To pack two 4-bit values a and b into one byte, put a in the high nibble using a << 4, then combine with b using bitwise OR.
  2. To unpack a byte x, recover the first value with (x >> 4) & 15 and the second with x & 15. Stop once you have produced n values.

Community answers

Answer by sincarawa

part 1 ` s = "AAABCCDDDD" def encode(s): rle = [] i = 0 n = len(s) while i < n: k = i + 1 while k < n and s[i] == s[k]: k += 1 rle.extend([f"{k-i}", s[i]]) i = k return ''.join(rle) def decode(encode: str): i = 0 n = len(encode) result = [] while i < n-1: k = encode[i+1] * int(encode[i]) result.append(k) i += 2 return ''.join(result) assert decode(encode(s)) == s `

Loading coding console...

Show the approach

Approach

The function dispatches on mode, sharing nothing between the two branches except the empty-string fast path.

Compress does a single left-to-right scan that counts maximal runs of identical characters. The loop index i runs from 1 to len(text) inclusive. As long as text[i] == text[i-1] the run continues and count grows. Otherwise we've hit a run boundary (or, when i == len(text), the end of the string), so we flush the just-finished run by appending str(count) and the run character text[i-1], then reset count = 1. Because i is allowed to reach len(text), the final run is always flushed without a separate post-loop step. Output is built in a result list and ''.join-ed at the end, which avoids the O(n²) cost of repeated string concatenation. Counts of 1 are emitted explicitly (e.g. 'Z' → '1Z'), matching the format.

Decompress inverts this. It walks the encoded string accumulating consecutive digit characters into a digits buffer. When a non-digit char appears, the buffered digits are the run length: it parses count = int(''.join(digits)), appends ch * count to the output, and clears the buffer. Validation makes it robust: a non-digit with no pending digits, a non-positive count, or leftover trailing digits each raise ValueError.

Why it's correct: compression writes exactly one <count><char> group per maximal run, and decompression reads exactly those groups back, so the two are inverses on well-formed input. The "no digits in raw text" rule guarantees every digit in the encoding belongs to a count, keeping decoding unambiguous.

Time complexity:
O(n) for compression (single pass over the input). O(m + k) for decompression, where m is the encoded length and k is the decoded output length.
Space complexity:
O(n) for the compression output. O(k) for decompression; the digit buffer holds at most O(log k) characters at a time.