Arrays and Hashing
13 / 170Arrays and HashingLesson 8 of 10About 44 min
A design problem about a question that has no correct answer in general: where does one piece end and the next begin?
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.
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.
def frame_numbers(numbers): out = [] for number in numbers: text = str(number) out.append(f"{len(text)}:{text}") return "".join(out) def unframe_numbers(data): result = [] i = 0 while i < len(data): j = data.index(":", i) # find the end of the length field width = int(data[i:j]) result.append(int(data[j + 1:j + 1 + width])) i = j + 1 + width # jump past the payload entirely return result print(frame_numbers([7, 42, 1000]))print(unframe_numbers(frame_numbers([7, 42, 1000])))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.
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 tests to see output.
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.