How does a serializer that emits references by identifier keep a cyclic object graph from driving its encoder into unbounded recursion?
answer
- a back-edge has no leaf
- remember what you have already written
- identity map, not equality map
- record the identifier before recursing
- one body per node, references after
basics
~20 sIt keeps an identity-keyed map of nodes already written. A node's first visit assigns an identifier, recorded before recursing, and writes the body once; every later encounter writes only a reference, so no body is written twice.
solid answer
~50 sA back-edge — module A depends on B, B depends back on A — sends a plain depth-first encoder around the loop forever, growing the stack and, if it streams, the output too. Identifier indirection breaks the loop with a map from node to identifier, keyed by object identity rather than field equality. The first time a node is reached the encoder assigns the next identifier, records it in the map **before** recursing into the node's fields, and writes the body with the identifier attached. Any later arrival finds the map entry and writes a short reference instead. Two properties make the walk terminate: the guard is consulted before a body is written, and a body is written at most once per node. Output is then linear in nodes and edges. The decoder mirrors it with an identifier-to-object map so every reference resolves to the same object.
code
pseudocode · 20 linesseen = empty identity map // node -> identifier
nextId = 1
function emit(node):
if seen contains node:
write reference to seen[node]
return
id = nextId
nextId = nextId + 1
seen[node] = id // recorded BEFORE recursing
begin body with identifier id
for each (name, value) in fields(node):
write name
if value is a node:
emit(value)
else:
write value
end bodygo deeper
Recall that references can form a loop, and that a value that follows every reference on a loop never finishes. Writing a loop out needs some memory of what has already been written.
Explain the identity map, why the identifier must be recorded before the recursion, and why output then scales with nodes and edges instead of with paths.
Show that you treat the reference convention as a published contract: what a downstream reader must now understand, why identifiers vary between runs, and when cutting one edge direction is the better trade than indirection.
Weigh a wire form that only your own libraries can read against one any consumer can parse, and decide which node classes deserve identity on the wire at all before reaching for a graph-aware encoder.
## What goes wrong without a guard A recursive encoder writes a node by writing its fields, recursing into any field that is itself a node. Give it a cycle — a build graph where module A depends on B and B depends back on A through a test fixture — and the recursion A, B, A, B never reaches a leaf. It does not hang quietly in every case: a buffering encoder typically exhausts the call stack first, while a streaming encoder can emit an unbounded amount of output before anything fails. Either way, the failure appears at the boundary between two processes, often for one production graph that happened to grow an edge back. Note that a cycle is the sharper form of the same defect as a node reachable by several paths. Both are cases of arriving at a node the encoder has already seen; the walk only survives the shared-node case because the graph eventually bottoms out. ## The mechanism **Reference-by-identifier indirection** has three parts: 1. An **identity map** from node to identifier. It must be keyed by object identity, not by field equality, or two distinct nodes that happen to hold equal fields would collapse into one and a cycle of equal-looking nodes would be misreported. 2. On first visit: take the next identifier, **record it in the map before recursing**, then write the node body with the identifier attached. 3. On every later visit: find the entry and write a reference carrying the identifier only. The ordering in step 2 is the part candidates get wrong. If the identifier is recorded after the children have been written, the node currently being written is not yet in the map, so a self-loop or a two-node cycle walks straight past the guard and recurses forever. The guard has to be able to see the node that is in progress. ## Why the walk terminates, and what it costs Let *n* be the nodes reachable from the root and *e* the edges between them. - Exactly **n** bodies are written: every node's first visit writes one, and no later visit writes another. - Every non-root node is discovered by exactly one edge, so **n - 1** edges carry bodies and the remaining **e - (n - 1)** edges each write a reference. - Total output is therefore about **e + 1** items — linear in *n* and *e*, rather than in the number of distinct root-to-node paths, which is what an unguarded walk pays. The encoder holds a map entry per distinct node for the duration of the walk, which is real memory on a large graph and the main runtime cost of the scheme. ## What the decoder has to mirror The decoder keeps an identifier-to-object map and returns the same object for every reference to a given identifier — that is what restores sharing, not merely termination. Because a cycle admits no ordering in which every node is defined before it is referenced, the decoder must also be able to accept a reference whose body has not arrived yet and fill the slot in later. ## Contract consequences, not implementation details | Consequence | Why it matters | |---|---| | Two node-shaped values exist on the wire: a definition and a reference | Every reader must understand the convention, so it belongs in the published contract | | Identifiers follow traversal order | The same graph can encode to different bytes on two runs, so payloads cannot be compared directly | | Identifiers are scoped to one payload | They are not entity keys and must not be stored or joined on by a consumer | | A reader that expects a plain nested document breaks | It sees a marker object where it expected the node's fields | Ecosystems differ in whether this convention is supplied by the encoding itself or has to be modelled by the schema author as an explicit identifier field plus reference fields; the mechanism underneath is the same either way. ## The alternative answers, and when they are right Cutting the cycle is legitimate too, and sometimes better: declare one direction of the edge non-travelling so the serialized form is a tree, and have the receiver rebuild the back-edge after decode from the direction that did travel. That keeps the wire form readable by any consumer and keeps the payload small, at the cost of a reconstruction step and a contract that says which direction is authoritative. What is never acceptable is relying on the graph being acyclic by luck, because nothing in the encoder enforces it.
- What breaks if the identity map is keyed by field equality instead of object identity?Two distinct nodes that happen to hold equal fields collapse into one on decode, which invents sharing the producer never had. In a cyclic graph it is worse: a node equal to one already on the stack is written as a reference back into the cycle, so the decoded graph has a loop the original did not. Identity is the only safe key.
- The encoder terminates but the decoded graph is still wrong. Where would you look?At the decoder's identifier map. If it constructs a fresh object per reference rather than resolving each identifier to one object, encoding was fixed and sharing was not, so the graph arrives as a tree with duplicates. Also check that identifiers are treated as payload-scoped; reusing them across messages merges unrelated nodes.
- Can you avoid the whole scheme by declaring one edge direction non-travelling?Often yes, and it is the simpler contract: serialize the child-to-parent direction out, and have the receiver re-attach it after decode from the direction that did travel. The payload stays a plain nested document any consumer can read. The price is a reconstruction step the contract must specify, and it only works where one direction is genuinely derivable.
saying these in an interview costs you the question
- Believes a cycle merely makes the payload larger
- Records the node identifier only after writing its children
- Keys the seen-map by field equality rather than identity
- Thinks encoders detect cycles automatically in every format
- Treats payload-scoped identifiers as durable entity keys
- Claims the decoder needs no map once encoding terminates