How do serialization and parsers work?

Before you start

This page belongs to the machine coding rounds guide, where serialization shows up as a coding task.

Why interviewers ask this

A serializer that works on friendly input and corrupts data on awkward input is a production bug, and that gap is what these questions expose. Candidates report three recurring tasks: code a key-value serializer where keys and values can contain any character, write a JavaScript Object Notation (JSON) parser and review it with the team, and serialize or verify a binary tree.

A weak answer joins strings with a comma and splits them back, and never tests a value that contains a comma. A strong answer names the rule that makes the round trip lossless, tests the empty string, a separator inside a value and a non-ASCII (American Standard Code for Information Interchange) character, and states the cost as linear in the input size. A Staff-level answer adds what happens on malformed or hostile input: reject it with a position, never guess, and never run code from it.

Serialization and parsers from first principles

Serialization

Serialization is the process of converting an in-memory data structure, such as a map or a tree, into a flat sequence of characters or bytes that can be stored or sent, so that the reverse step, called deserialization, can rebuild an equal structure from it later.

Parser

A parser is a program that reads a sequence of characters or bytes from left to right, checks each part against a format's grammar, and either builds a data structure from it or reports an error at the position where the input stops following the rules.

Length prefix

A length prefix is a number written before a string that says how many bytes follow, so a reader takes exactly that many bytes without searching for a closing marker, and the string can hold any character at all.

In plain words

Think of posting a parcel with a packing slip. The slip says "three items: a book, a mug, a scarf". The receiver does not guess where one item ends; the slip tells them. The analogy breaks in one place: a person can improvise, while a parser follows its rules exactly and fails on the first line that does not match.

In one precise sentence, serialization maps a structure to a string so that a deterministic parser can map it back to an equal structure. A grammar is the set of rules that says which strings are valid in a format and how they break into parts.

Step 1: The grammar fixes what a value can be

A format starts with a grammar. The JavaScript Object Notation (JSON) grammar in Request for Comments (RFC) 8259, a standard from the Internet Engineering Task Force (IETF), describes objects, arrays, strings, numbers and the three words true, false and null. Your own formats need the same discipline: list the shapes a value can take before writing code.

For a key-value store, the shapes are: a sequence of pairs, each pair a key string and a value string. For a binary tree, the shapes are: empty, or a value followed by a left tree and a right tree. Input: a description of your data. Output: a list of shapes. You now know what the serializer must write and the parser must accept. Nothing in the grammar says how a string ends; the next step decides that.

Step 2: A length prefix marks where each string ends

The serializer writes each string as its byte length, a separator, then the bytes. A reader that sees the number takes exactly that many bytes, whatever they contain, so a comma, a colon, a quote or a newline inside a value cannot confuse it. This is the answer to "key and value can contain any character".

The other common fix is escaping, which is rewriting each special character as a longer sequence so it cannot be mistaken for a separator. JSON uses it: RFC 8259 says the quotation mark, the backslash and the control characters U+0000 through U+001F must be escaped inside a string. Escaping works, but the reader must track whether the previous character was an escape.

Count bytes, not characters: write the length of the encoded form (for example Unicode Transformation Format 8-bit, UTF-8, which RFC 3629 defines as one to four bytes per character), or a reader decoding bytes will drift. Input: strings. Output: one flat byte sequence.

Step 3: The parser reads with a cursor

The parser keeps one position, the cursor, and only moves it forward. For the length-prefixed format the loop is: read digits up to the separator, convert them to a number n, take the next n bytes as a string, move the cursor past them, repeat until the end. Every step consumes input, so the total work is linear in the input size.

For a recursive format such as a tree, the parser calls itself: read one token (a token is one comma-separated piece, a number or #); if it marks an empty tree, return nothing; otherwise read the left subtree, then the right. Input: a flat sequence. Output: the rebuilt structure. A JSON parser is the same idea with more shapes: the next character decides which shape follows, and the parser calls the matching routine for objects, arrays, strings or numbers.

Step 4: The parser rejects what the grammar forbids

A parser that guesses past an error hides the bug until later. Instead it stops where the input breaks the grammar, and reports the position: a length that runs past the end, a missing separator, a tree that ends before every slot is filled.

Even a valid grammar leaves edge cases to decide. RFC 8259 says object names should be unique, that behaviour on repeated names is unpredictable, and that many implementations keep only the last pair. It also allows implementations to limit the range and precision of numbers, and gives 1E400 as an example that may cause interoperability problems. Decide your own policy, write it down and test it. Input: a possibly bad sequence. Output: a structure or a precise error.

Worked example

The input is four key-value pairs (illustrative): name is Ada, note is a,b:c, empty is the empty string, and city is Zürich €. The raw text of all keys and values is 36 bytes in UTF-8.¹

The naive format joins each pair as key:value with commas between pairs. It fails the round trip: the value a,b:c contains both separators, so splitting on commas cuts it in two.¹ The length-prefixed encoding is 4:name3:Ada4:note5:a,b:c5:empty0:4:city11:Zürich €. It decodes back to the same four pairs, and takes 53 bytes.¹ The value Zürich € has eleven bytes because the letter ü takes two bytes and the euro sign takes three.¹

Now a tree. The binary tree with root 1, left child 2 (children 4 and 5) and right child 3 has five nodes. Preorder with a marker # for each empty child gives 1,2,4,#,#,5,#,#,3,#,#, which is eleven tokens, one more than twice the node count, and rebuilds the identical tree.¹

To verify such a string without building the tree, keep a count of open slots, starting at one. Each token fills a slot; a node token opens two new ones. The count after each token is 2, 3, 4, 3, 2, 3, 2, 1, 2, 1, 0, and the string is valid because it reaches zero exactly at the last token.¹ The input 1,# ends with one slot still open, and #,1,#,# fails at its second token because no slot is left.¹ One pass with one counter is linear time, and constant extra space if you scan the string for commas instead of calling split, which builds a list of every token.

def lp_encode(pairs):
    parts = []
    for k, v in pairs:
        for s in (k, v):
            b = s.encode("utf-8")           # count bytes, not characters
            parts.append(str(len(b)).encode() + b":" + b)
    return b"".join(parts)                   # join once, not += in a loop

def lp_decode(data):
    items, i = [], 0
    while i < len(data):
        j = data.find(b":", i)
        if j < 0:
            raise ValueError(f"missing separator after byte {i}")
        if not data[i:j].isdigit():          # rejects empty, signed or non-numeric lengths
            raise ValueError(f"bad length at byte {i}")
        n = int(data[i:j])
        if j + 1 + n > len(data):
            raise ValueError(f"length {n} at byte {i} runs past the end")
        items.append(data[j + 1:j + 1 + n].decode("utf-8"))
        i = j + 1 + n                        # the cursor only moves forward
    if len(items) % 2:
        raise ValueError("odd number of strings")
    return [(items[x], items[x + 1]) for x in range(0, len(items), 2)]

The decoder moves its cursor past each byte once, so it is linear in the input size. In Python, bytes are immutable, so repeated += copies the buffer each time; collecting parts in a list and joining once keeps the encoder linear. The three checks reject a missing separator, a length that is not plain digits (so -1 fails) or runs past the end, and an odd number of strings, each with a position or a clear message.

Trade-offs and edge cases

Each way of marking a string's end trades simplicity, readability and safety. A bare delimiter is simplest and wrong for arbitrary data. Escaping keeps the text readable, as in JSON, but needs state in the reader. A length prefix handles any bytes, but a person cannot read it, and one wrong count corrupts everything after it.

Edge cases to test: the empty string (length zero, as in 0: above), a value that looks like a length, a multi-byte character, a key repeated twice, and input cut off mid-value. A graph with cycles or shared nodes needs more than a tree format: give each node an id and write references to ids, or the writer never stops. The same idea of parsing structured text appears in event and log processing problems, and a store you must save and restore appears in the in-memory database assessment and the least recently used (LRU) cache design. Other low-level design questions ask for the same split of encoding and policy.

Format choice also has a safety side. The Python documentation warns that the pickle module is not secure: malicious pickle data can execute arbitrary code during unpickling, so only data you trust may be unpickled. A text format such as JSON builds only plain data, which is why it is the usual choice for input from outside. Recursive parsers also need a plan for deeply nested input, such as a depth limit.

How to answer it in an interview

The spoken structure: reject delimiters, state the length-prefix format, give the cost, then name your tests and the error policy.

Common mistakes

• "I will join pairs with a comma and a colon." (wrong) A value can contain both. (right) "I use length prefixes, or escape the separators and the escape character itself."
• "The length is the number of characters." (wrong) The reader takes bytes, so a multi-byte character breaks the count. (right) "I write the length of the encoded bytes."
• "Parsing is just splitting the string." (wrong) Nested formats need a cursor and recursion. (right) "I parse with a cursor and call a routine per shape."
• "On bad input I return what I have." (wrong) Half a structure looks valid and spreads the bug. (right) "I stop with an error and the position."
• "Deserializing is always safe." (wrong) Some formats run code while loading. (right) "I use a data-only format for untrusted input."

def serialize(node):                         # node is (value, left, right) or None
    parts = []
    def walk(n):
        if n is None:
            parts.append("#")
            return
        parts.append(str(n[0]))
        walk(n[1])
        walk(n[2])
    walk(node)
    return ",".join(parts)

def deserialize(text):
    def build(it):
        tok = next(it)
        if tok == "#":
            return None
        return (int(tok), build(it), build(it))   # left is read before right
    return build(iter(text.split(",")))