Word Compression Algorithm

Q: Word Compression Algorithm

This question evaluates a product manager's ability to reason about string compression and decompression techniques (run-length encoding), focusing on algorithmic trade-offs, correctness under edge cases, and time/space complexity analysis.

Q: How do I approach Product / Decision Making interview questions?

Product / Decision Making questions require understanding of core concepts and practice. PracHub provides solutions with explanations to help you master product / decision making interviews.

Question

String Compression and Decompression (Run-Length Encoding)

Problem

Design an algorithm that compresses a string by replacing consecutive repeating characters with the character followed by the repeat count. For example:

Input: "aaabbc"
Output: "a3b2c1"

Describe both the compression and decompression procedures.

Requirements

Define the compression algorithm (encode) and the decompression algorithm (decode).
Address edge cases:
- Single-character runs (e.g., "c" → "c1").
- Very long inputs and runs (e.g., millions of characters).
- Cases where compression does not help or makes the string longer.
Provide Big-O time and space complexity analysis.

Assumptions (make minimal, explicit choices)

Use a simple run-length encoding (RLE) scheme: for each run, emit a single character followed by its run length as a base-10 positive integer (no separators). Always include the count (even when it is 1), consistent with the example.
Characters are Unicode code points; counts are ASCII digits 0–9.
Input strings can include any characters, including digits; the format remains unambiguous because decoding reads exactly one character followed by one-or-more digits representing the count.

Word Compression Algorithm

String Compression and Decompression (Run-Length Encoding)

Problem

Requirements

Assumptions (make minimal, explicit choices)

Solution

Comments (0)