Week 1 · Arrays & Hashing

Encode and Decode Strings

Design a reversible representation for a list of strings, including empty strings and strings containing delimiter-like characters.

Medium Arrays & Hashing Week 1 Practice runner

Frame the problem

The encoded string must be unambiguous.
Strings can contain punctuation, digits, and delimiters.
The decoder must know exactly where each string ends.

1. Reveal example inputs and outputs

Example 1

Input:

encode_and_decode([
  "lint",
  "code",
  "love",
  "you"
])

Output:

[
  "lint",
  "code",
  "love",
  "you"
]

Example 2

Input:

encode_and_decode([
  "a#b",
  "",
  "12:34"
])

Output:

[
  "a#b",
  "",
  "12:34"
]

2. Brute force first

Why does joining with a delimiter fail when strings can contain that delimiter?

3. Reveal the insight ladder

Prefix each string with its length.
Separate length and payload with a delimiter.
During decode, read digits until delimiter, then consume exactly that many characters.
Repeat until the encoded string is exhausted.

4. Dry run before code

['a#b', '', 'xy'] encodes as '3#a#b0#2#xy'.
Decoder reads length 3, then a#b.
Then length 0, then empty string, then length 2 and xy.

5. Reveal final Python solution

def encode_and_decode(strs):
    def encode(values):
        return "".join(f"{len(value)}#{value}" for value in values)

    def decode(payload):
        result = []
        i = 0
        while i < len(payload):
            j = payload.index("#", i)
            size = int(payload[i:j])
            start = j + 1
            result.append(payload[start:start + size])
            i = start + size
        return result

    return decode(encode(strs))

Complexity: Time O(total characters), space O(total characters) for the encoded payload and decoded output.

Interview narration

The design problem is about making boundaries explicit.
A length prefix makes the payload safe even if it contains the delimiter.
The decoder advances by parsed length, not by searching for the next delimiter in the payload.

Common traps

Joining with a delimiter and splitting later.
Forgetting empty strings.
Searching for payload delimiters instead of consuming the exact length.

Follow-up drills

1. Could the delimiter be any character?

Yes, because the delimiter only separates the length from the payload. The payload itself is consumed by length, so it may contain the delimiter safely.

2. What if strings are bytes rather than text?

Use byte lengths and a byte delimiter, or encode the length as a fixed-size header. The same boundary principle applies.

Interactive runner

Write the required Python function. Your code runs locally in this browser. Hints reveal one failing case at a time.