Implement RLE and bit-packing compression

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.