What does a tree-walking encoder produce, on the wire and after decode, when one build-graph node is reachable from three parents?
answer
- the writer assumed a tree
- one node, three paths in
- equal fields, different objects
- update through one parent only
- identifier first, reference after
basics
~20 sA tree walk writes that shared node's body once per path, so the wire carries three copies and decoding rebuilds three distinct objects with equal fields. Sharing is lost: a later change through one parent is invisible through the other two.
solid answer
~50 sA depth-first walk with no identity map cannot tell a second visit from a first, so it writes the shared node's body once for every path that reaches it. On the wire that is three copies; after decode it is three separate objects whose fields happen to be equal. If the node is immutable that costs only bytes, but if it is mutable or identity-bearing it is a correctness bug: a write through one parent is not seen through the others, an invariant that assumed a single instance is now held three times, and consumers that compared by reference now see three different nodes. Cost also scales with the number of *paths* rather than the number of nodes. The fix is identity indirection: give each node body an identifier the first time it is written, emit later encounters as a reference to that identifier, and let the decoder return one object per identifier.
go deeper
Recall that a reference in memory is a link, not a copy, and that writing a value out follows those links. Two objects can hold equal fields and still be different objects.
Explain why a depth-first walk with no identity map writes a twice-reachable node twice, what the decoded graph then looks like, and how an identifier plus later references restores one object per node.
Show that you have debugged the symptom: a write through one parent that another parent never sees, or an encode whose cost grows with path count. Say how you would confirm it from a payload and what you would change in the contract.
Frame it as a contract decision rather than a library setting: which node classes carry identity that consumers may rely on, what obligations reference indirection places on every reader, and what that costs when a consumer cannot be upgraded with you.
## The shape mismatch A serializer turns a value into a linear byte stream. An in-memory value is not linear: it is a **directed graph** whose nodes are objects and whose edges are references. A recursive encoder that writes each field as it meets it, recursing into fields that are themselves nodes, implicitly assumes that graph is a **tree** — that every node is reachable from the root by exactly one path. Real graphs break that assumption in two ways: a node reachable from several parents (a **shared** node, the diamond), and a path that returns to a node already being written (a **cycle**). This question is the first case. Take a build graph: three modules each depend on one shared library node. In memory there is one library object and three references to it. A tree walk writes the library node's body three times, because the second and third visits look exactly like the first. ## What actually changes across the round trip | Property | In memory | After a tree-walking round trip | |---|---|---| | Library node objects | 1 | 3 | | Bytes spent on it | one body | three bodies | | Reference equality between the parents' fields | the same object | three distinct objects | | A field written through parent A | visible via B and C | visible only via A | | Encoder work | proportional to nodes and edges | proportional to distinct paths | ## Why it is more than a size problem - **Divergent update.** The commonest production symptom: code updates the node through one parent, reads it back through another, and sees the old value. Nothing errors; the data is simply wrong. - **Broken single-instance invariants.** A counter, a cached credential, a status flag or 'the' configuration node that the design assumed existed once now exists three times, each drifting. - **Identity comparisons flip.** A consumer that deduplicated by reference identity now sees three nodes where the producer had one. - **Path-count blow-up.** Duplication compounds. Stack *k* diamonds above one leaf and each level doubles the number of paths, so the leaf's body is written **2^k** times — a graph of a few dozen nodes can produce a payload of millions. The encoder's running time grows the same way, which is why this often shows up first as an encode that never finishes rather than as a wrong read. The duplication is harmless in exactly one case, and it is worth naming it because it is the basis of the design decision below: when the node is an immutable value with no identity of its own — a version string, a timestamp, a checksum — three copies are observationally the same as one. Even the byte cost is partly recovered, since repeated byte sequences are highly compressible by dictionary-based algorithms such as DEFLATE or Zstandard. ## Making identity survive the wire The standard remedy is **reference-by-identifier indirection**, in three steps: 1. Keep a map from node to identifier, keyed by **identity**, not by field equality — two structurally equal but distinct nodes must receive different identifiers. 2. On the first visit, assign the next identifier, record it in the map, and write the node body with that identifier attached. 3. On every later visit, write a short reference carrying the identifier instead of the body. The decoder mirrors this with an identifier-to-object map and returns the same object for every reference to a given identifier. Output then becomes linear in nodes and edges rather than in paths. This is not free, and the costs belong in the conversation: - The wire form now has **two kinds of node-shaped value**, a definition and a reference. Every reader has to understand that convention, so it is part of the contract, not an implementation detail. A reader expecting a plain nested document sees a marker object it cannot interpret. - Identifiers follow traversal order, so two encodings of the same graph can hand out different identifiers and differ byte for byte. - The encoder holds an identity-keyed map sized by the number of distinct nodes. Some encoding families supply this convention themselves; others leave it to the schema author, who must model it explicitly as an identifier field plus reference fields. Where ecosystems differ, they differ in whether the convention is built in, not in the underlying mechanism. ## What an interviewer is listening for That you name the tree assumption rather than calling it a bug in the library; that you distinguish the size symptom from the divergent-update symptom; and that you can say which nodes in a given graph actually need identity preserved and which are values that may safely be copied. That last judgment is the design decision the mechanism exists to serve.
- How would you spot this duplication in a payload you did not write?Look for the same node body repeated verbatim in different branches, and compare the payload's size and node count against the number of distinct entities you expect. A payload that grows far faster than the data does, or one whose distinct-entity count is much lower than its node count, is the signature. Encode time growing superlinearly with graph depth points the same way.
- Does the duplication matter when the shared node is immutable?Usually not for correctness: with no mutation there is no divergent update, and a value with no identity of its own is observationally the same whether it arrives once or three times. It still costs bytes and decode allocations, though much of the byte cost is recovered by a dictionary-based compressor. The decision is therefore per node class and belongs in the wire contract.
- The producer's graph is a tree today. Is it safe to keep the tree-walking encoder?Only while it stays a tree, and nothing on the wire enforces that. The first time a model change makes a node reachable twice, the encoder silently starts duplicating instead of failing. If the shape matters, either assert it at encode time or adopt identifier indirection up front, since retrofitting it later changes the contract every reader depends on.
Photocopying a shared address book page into three folders: every folder reads the same numbers today, and the day someone corrects one page the other two quietly stay wrong.
saying these in an interview costs you the question
- Assumes any object graph can be walked as a tree
- Says the decoder deduplicates objects whose fields are equal
- Treats equal contents after decode as restored sharing
- Names only payload size, missing the divergent-update bug
- Believes only cycles break a walker, not shared nodes
- Expects the encoder to fail loudly rather than duplicate silently