Arrays and Hashing
Framing a string so it can be split back
A design problem about a question that has no correct answer in general: where does one piece end and the next begin?
The situation
You have several pieces of data and one channel to send them down. Flattening them together is easy. Getting them apart again, reliably, is the part that needs thought.
Gotcha
The first idea, and why it fails
Join with a separator such as a comma and split on it. This works right up until a piece of data contains a comma, at which point the split happens in the wrong place. Every choice of separator has the same flaw whenever the data is allowed to contain arbitrary characters.
Escaping the separator does work, but then you have to escape the escape character, and the reader stops being three lines. It is a legitimate answer worth naming; it is not the clean one.
Why it works
Say how long it is, up front
Instead of marking where a piece ends, declare its length before it starts. The reader then never has to search inside the data at all: read the length, then take exactly that many characters without looking at them.
That property is the whole idea, and it is worth being able to state on its own: a correct framing scheme lets the reader skip the payload rather than scan it.
Here is the idea applied to a simpler case, framing a list of integers so that the reader knows how many digits to take. Notice that the reader never inspects the digits it copies.
Tip
Read that encoded string carefully
It is 1:72:424:1000. A human finds it hard to parse because the digits run together, and the reader does not care at all: it takes one character, then two, then four, because each length told it exactly what to do.
This is why the scheme survives payloads containing colons, digits, or anything else. The reader is never searching.
Edge cases
The cases that break naive attempts
An empty piece of data. An empty collection. A piece made entirely of digits. A piece containing the delimiter. A piece containing something that itself looks like a valid length prefix.
Length prefixing handles all of them. Before you write your own version, decide what each of those should produce, then check that your scheme agrees.
Where this comes back
This exact idea returns in Unit 8 for serializing a binary tree. Network protocols solve the same problem the same way, which is why length-prefixed framing is worth recognizing by name.
It is also why interviewers like a problem with no algorithmic content. Candidates who propose a delimiter, get told the payload can contain it, and then propose a rarer delimiter have answered the wrong question.
Frame a nested structure
Length prefixing composes, which is the property that makes it worth knowing. Write pack and unpack for a list of pairs of strings, so each pair is framed and each string inside it is framed too. Round-tripping must return the original list exactly, including pairs with empty strings and strings containing your delimiter.
Tests
cases = [
[("a", "1"), ("bb", "22")],
[("key:with:colons", "3|4")],
[("", "")],
[],
[("x", ""), ("", "y")],
]
for case in cases:
print(unpack(pack(case)) == case)Output
Run the tests when you are ready.
Encode And Decode Strings
Read the constraints first and let them tell you what complexity is expected. Derive the approach, implement it, run the tests, and submit when it passes.