##### Question Design an algorithm that compresses a string by replacing consecutive repeating characters with the character followed by the repeat count (e.g., "aaabbc" → "a3b2c1"). Describe the compression and decompression procedures. Specify how you would handle edge cases such as single-character runs, very long inputs, or cases where compression makes the string longer. Provide Big-O time and space complexity analysis.

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.

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.

What difficulty level is this interview question?

This is a medium difficulty Product / Decision Making question, commonly asked during Take-home Project rounds at Goldman Sachs.

What role is this question designed for?

This question is commonly asked for Product Manager candidates at Goldman Sachs during technical interviews.

Word Compression Algorithm | Goldman Sachs Interview 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.

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

Quick Overview

String Compression and Decompression (Run-Length Encoding)

Problem

Requirements

Assumptions (make minimal, explicit choices)

Solution

Comments (0)

Word Compression Algorithm

Quick Overview

String Compression and Decompression (Run-Length Encoding)

Problem

Requirements

Assumptions (make minimal, explicit choices)

Solution

Comments (0)