MySmartCoPilot
Ask Passes Your pass 7 days left 1 day left Last day

Your country

Tools that support it use your country for local currency, number formats, units and paper size. Your choice is saved only in this browser.

Coding Interview Patterns  Module 3 – Arrays and hashing

Encoding lists of strings safely

Turn any list of strings into one string and back without loss: why a separator breaks, length-prefix framing, escaping, and counting in the same unit.

  • Intermediate
  • 20 minutes
  • Examples run with Python 3.14.8, Pyodide 314.0.7, Node.js 24.21.0 and quickjs 0.32.0
  • By MySmartCoPilot
Free: The problem: a shopping list in one string. With a pass: the other 10 sections and 3 interview answers, about 16 minutes.

What you will learn

  • Serialise a list of arbitrary strings into one string that decodes exactly
  • Compare length-prefix framing with escaping by size, speed and robustness
  • Explain why the encoder and the decoder must count lengths in the same unit
  • Test a codec with empty strings, separator characters and non-ASCII text

Before you start

What you’ll learn · Before you start

What you will learn

  • Serialise a list of arbitrary strings into one string that decodes exactly
  • Compare length-prefix framing with escaping by size, speed and robustness
  • Explain why the encoder and the decoder must count lengths in the same unit
  • Test a codec with empty strings, separator characters and non-ASCII text

Before you start

On this page

A list of strings is encoded safely when it becomes one string from which a decoder gets back exactly the same list, for every list there is: joined with commas, ["a,b", "c"] and ["a", "b,c"] both become a,b,c, and no decoder can tell them apart. To encode and decode strings safely, the decoder must know where each string ends without trusting what the strings contain. Two methods give it that. length-prefix framing: Writing each item's length in front of it, as in 5#hello, so that a reader knows where the item ends without looking at what it contains. writes each string’s length in front of it, as in 5#hello, so the decoder knows how much to take without looking inside. Escaping marks every separator that occurs inside a string, so that only an unmarked separator can end one. Both encode and decode strings of any content in one left-to-right pass.

The problem: a shopping list in one string

The problem

A shopping-list app keeps its list in the browser’s local storage, which stores only strings, so the list has to become one string and come back later. Write an encoder that turns any list of strings into one string, and a decoder that turns it back into exactly the same list: the same strings in the same order, empty ones included. A string may contain any character: commas, #, digits, quotes, line breaks, emoji, any script. No library serialiser.

Constraints: up to 10⁴ strings and 10⁵ characters in all; both directions in time linear in the total length.

  • ["milk", "eggs, 12", "#2 pencils"]: a comma and a # inside strings.
  • [] and [""]: no strings, and one empty string, must encode differently.
  • ["a,b", "c"] and ["a", "b,c"] must encode differently too.
  • ["दूध", "🥛"]: milk in Hindi, then the glass-of-milk emoji.
The lists ["a,b", "c"] and ["a", "b,c"] both join into the string a,b,c, which splits into a third list, ["a", "b", "c"].["a,b", "c"]["a", "b,c"]join with a commaa,b,csplit on commas["a", "b", "c"]a third list: neither one comes back

Two lists, one joined string, and a third list back

Text description of the diagram

At the top are two different lists: the first holds the strings "a,b" and "c", the second holds "a" and "b,c". Joining either list with a comma gives the same string, a,b,c, shown once in the middle with an arrow from each list.

Splitting a,b,c on its commas, shown at the bottom, gives a third list, "a", "b" and "c", in a dashed box: neither of the two lists the string came from comes back.

The obvious way: join on a comma, split on a comma

Join the strings with a comma, and split on commas to decode. Each direction is one pass, and the round trip breaks:

Join on a comma, split on a comma Python · naive/join_split.py 
"""Joining a list on a comma and splitting it again: where the round trip breaks."""
import random


def encode(items):
    return ",".join(items)


def decode(text):
    return text.split(",")


for items in (["milk", "bread"], ["eggs, 12", "#2 pencils"], ["a,b", "c"], ["a", "b,c"], [], [""]):
    text = encode(items)
    back = decode(text)
    print(f"{items!r:26} -> {text!r:22} -> {back!r:26} {'same' if back == items else 'DIFFERENT'}")

rng = random.Random(9)
lists = [["".join(rng.choice("ab,#") for _ in range(rng.randint(0, 3))) for _ in range(rng.randint(0, 4))] for _ in range(1_000)]
wrong = [items for items in lists if decode(encode(items)) != items]
with_comma = sum(any("," in s for s in items) for items in wrong)
empty = sum(items == [] for items in wrong)
print(f"1,000 random lists of up to 4 strings made of a, b, ',' and '#': {len(wrong)} come back different")
print(f"  {with_comma} of them have a comma inside a string, {empty} are the empty list, {len(wrong) - with_comma - empty} are neither")

Output

['milk', 'bread']          -> 'milk,bread'           -> ['milk', 'bread']          same
['eggs, 12', '#2 pencils'] -> 'eggs, 12,#2 pencils'  -> ['eggs', ' 12', '#2 pencils'] DIFFERENT
['a,b', 'c']               -> 'a,b,c'                -> ['a', 'b', 'c']            DIFFERENT
['a', 'b,c']               -> 'a,b,c'                -> ['a', 'b', 'c']            DIFFERENT
[]                         -> ''                     -> ['']                       DIFFERENT
['']                       -> ''                     -> ['']                       same
1,000 random lists of up to 4 strings made of a, b, ',' and '#': 651 come back different
  418 of them have a comma inside a string, 233 are the empty list, 0 are neither

Recorded with Python 3.14.8 on macOS 26 arm64. To run it yourself: mise exec python@3.14.8 -- python3 join_split.py

The lists ["a,b", "c"] and ["a", "b,c"] both become a,b,c, so no decoder can tell which was meant: the information is gone. The empty list and the list of one empty string both become the empty string. Of 1,000 random lists, 651 came back different, each because a string held a comma or the list was empty. A rarer separator, such as | or an invisible control character, only makes the failure rarer: it is still a character a string may contain. Step through the four lists of the figure:

Interactive · step by step Two lists, one joined string, and a third list back Step through four lists. Each one is joined with a comma, and the joined text is split on commas to decode it.
Two lists, one joined string, and a third list back, step 6 of 6. Showing list ["a,b", "c"], list ["a", "b,c"], empty list [], list [""], joined text (a,b,c for both lists), split back (["a", "b", "c"]), joined text (empty text for both), split back ([""], one empty string). In focus: split back, split back.list ["a,b", "c"]list ["a", "b,c"]empty list []list [""]joined texta,b,c for both listssplit back["a", "b", "c"]joined textempty text for bothsplit back[""], one empty string

The drawing shows the whole scene; its 6 steps are listed below.

Every step as text
  1. Joining ["a,b", "c"]. Joining puts a comma between the strings, so ["a,b", "c"] becomes a,b,c, with the comma that was inside the first string next to the one between them.
  2. Joining ["a", "b,c"]. The second list joins to the same text, a,b,c. Two different lists now share one encoding.
  3. Splitting it back. Splitting a,b,c on its commas gives ["a", "b", "c"], a third list. No decoder can tell which list was meant: the information is gone.
  4. The two empty cases. The empty list joins to the empty text, and so does the list of one empty string.
  5. Splitting the empty text. Splitting the empty text gives [""], one empty string, so the empty list comes back as a list of one string.
  6. What went wrong. A comma inside a string looks exactly like a comma between strings, so the decoder cannot find the ends by searching the text.

What to notice

A separator inside a string looks exactly like a separator between strings, as the figure shows, so the decoder must not find the ends by searching the content. Either it learns each string’s length before the string starts, or every string is rewritten so that it cannot contain an unmarked separator. A length then raises one more question, which unit it counts, because Python, JavaScript and Go measure the same text differently.

Checkpoint

Check: Any list of strings, in one string and back · Why joining on a separator breaks · Finding each end without searching the content

  1. Question 1 of 3 Which two lists must the encoder turn into different strings?

    Choose one answer.

    Show the answer

    Answer: [] and [""]

    An encoding is safe only if every list has its own text, so [] and [""], and ["a,b", "c"] and ["a", "b,c"], must all encode differently.

  2. Question 2 of 3 What do ["a", "b,c"] and ["a,b", "c"] each join to, with a comma between the strings?

    Choose one answer.

    Show the answer

    Answer: Both join to a,b,c

    Two different lists share one encoding, so no decoder can tell which was meant, as the figure shows.

  3. Question 3 of 3 A colleague suggests a separator nobody types, such as an invisible control character. Why does that not make the encoding safe?

    Choose one answer.

    Show the answer

    Answer: It is still a character, so some string may contain it, and then the decoder cannot tell it from a separator

    A safe decoder must find where each string ends without searching the content: it learns each length first, or every separator inside a string is marked.

The practice below starts with whatever you know least.

Practice that adapts to you

Practise this lesson

9 questions about 10 ideas of this lesson. Each answer is explained at once, and what you get right is kept in this browser.

  1. Question 1 of 9 What must decode(encode(x)) give for every list x?

    Choose one answer.

    Show the answer

    Answer: Exactly x, the same strings in the same order, empty ones included

    A round trip is exact or it is broken: decode(encode(x)) == x for every list x.

  2. Question 2 of 9 Which strings may the shopping list hold?

    Choose one answer.

    Show the answer

    Answer: Any string at all, commas, digits, line breaks, emoji and any script included

    Because any character may appear, no character can be a safe separator on its own.

  3. Question 3 of 9 A format encodes [] and [""] the same way. What can a decoder of that format do?

    Choose one answer.

    Show the answer

    Answer: Nothing right for both; whatever it returns for that text is wrong for one of the two lists

    Any two lists that share an encoding make the codec wrong for one of them, which is why every list needs its own text.

  4. Question 4 of 9 What does splitting the empty string on commas give, in Python?

    Choose one answer.

    Show the answer

    Answer: [""], a list of one empty string

    So the empty list cannot survive a join and a split: it comes back as one empty string.

  5. Question 5 of 9 Of 1,000 random lists of up to four strings made of a, b, a comma and #, how many came back different in the run?

    Choose one answer.

    Show the answer

    Answer: 651, each because a string held a comma or the list was empty

    Most lists broke, and every broken one had a comma inside a string or was the empty list, as the run printed.

  6. Question 6 of 9 Joining with "|" instead of a comma: which list then breaks?

    Choose one answer.

    Show the answer

    Answer: Any list with a | inside a string, and the empty list

    Changing the separator moves the failure to another character; it never removes it.

  7. Question 7 of 9 What are the two ways to let a decoder find where each string ends?

    Choose one answer.

    Show the answer

    Answer: Write each string's length in front of it, or escape every separator that occurs inside a string

    Length-prefix framing and escaping both let the decoder find each end without trusting the content.

  8. Question 8 of 9 A length written in front of each string raises one more question. Which?

    Choose one answer.

    Show the answer

    Answer: Which unit the length counts, since Python, JavaScript and Go measure the same text differently

    The same word has a different length in each unit, so the encoder and the decoder must agree on one.

  9. Question 9 of 9 Why does searching the joined text for separators fail, however clever the search?

    Choose one answer.

    Show the answer

    Answer: A separator inside a string looks exactly like a separator between strings, so the text alone does not say which it is

    The joined text holds less information than the list, so the decoder must be told where the ends are.

Length-prefix framing, step by step Pro

In this part:

  • A dry run
  • Why the decoder always gets the list back
  • The same codec in 14 languages
  • When the two sides count differently
  • Escaping, the other way, and how the two compare
  • The decoder that copies the whole wire, again and again
  • Edge cases, tests and variants
    • Edge cases and the tests that catch them
    • Variants
  • Practice: a codec of your own
    • A codec that survives any list of strings
  • Interview questions
    • Why is joining strings with a separator not a safe way to encode a list of strings, even with a rare separator?
    • A Python service sends lists of strings to a JavaScript web client and a Go worker as one text field. The strings are user input in any language. Define the format precisely enough that all three decode every list the same way, and say how you would show that they agree.
    • Your length-prefixed decoder now reads files that users upload. What can a malformed or hostile input do to it, and how do you make the decoder safe without slowing down valid input?
    • You must store 10 million short strings, about 12 bytes each, in one file and later read any single string by its position quickly. Compare length-prefix framing, escaping, and framing with an index of offsets, by file size and by the cost of reading string number 7,000,000.
  • Key takeaways

2 diagrams · 6 runnable examples (Python) · 1 exercise with sample tests · 3 interview answers · about 47 minutes

Opening this part with your pass…

This part opens with any MySmartCoPilot pass.

  • Pro pass · 1 week₹79$2.99
  • 30 days₹179$5.99
  • 1 year₹1,699$45

One payment; a pass never renews. The price shown is the total you pay: no fees or charges are added at checkout.

Choose a passI have a licence key

It also opens every other in-depth part in Learn and every Pro tool. Sales are final, except where the law gives you a right to withdraw, for example in the EU and the UK (refund policy).

Terms in this lesson

escape character
A character that changes the meaning of the character after it, such as a backslash written before a comma to make the comma part of the text instead of a separator.
length-prefix framing
Writing each item's length in front of it, as in 5#hello, so that a reader knows where the item ends without looking at what it contains.

References

Related tools

Python Online Compiler Real CPython in your browser — with stdin, files and a stop button. JavaScript & TypeScript Online Compiler Write, run and debug JS or TS snippets — safely sandboxed, nothing to install. Text to Binary & Hex Converter See the exact bytes behind any text, and turn binary or hex dumps back into text.

Report a problem with this lesson