Deep Clone, Constraint by Constraint
The incremental-coding round again, on a problem where stage three genuinely breaks the obvious design: copy an object, then nested structures, then one containing a cycle, then one where two keys must still share the same clone. Tests whether your first version can absorb the next requirement.
The problem
Implement deep_clone(value) / deepClone(value) through four stated stages. (1) Copy a flat object of primitives. (2) Recurse into nested objects and arrays, so no nested container is shared with the source. (3) Handle a structure containing a cycle without overflowing the stack. (4) Preserve shared identity: if two properties of the source referenced the same object, the corresponding properties of the clone must reference the same clone. Primitives, null, and non-container values are returned as-is.
{ a: 1, b: "x" }an equal but distinct objecto.self = oclone.self === clones = {}; { a: s, b: s }out.a === out.b- Never return the same container object the caller passed in.
- A cycle must not overflow the stack, and the cycle must close onto the clone rather than the original.
- Two source properties pointing at one object must produce two clone properties pointing at one clone.
- Primitives and
nullare returned unchanged; arrays must clone as arrays.
Your turn — write it
Edit the stub, hit Run (or ⌘/Ctrl + Enter), and watch the hidden tests. Stuck? the hints are right above and Reveal solution is one click away.
Implement deep_clone / deepClone satisfying all four stages at once.
- Keep a map from each original container to its clone, and check it before you recurse.
- A visited *set* stops the crash and loses shared identity — you need the original-to-clone *map*.
- Create the empty clone and record it in the map before filling in its properties, or the cycle never terminates.
- Arrays are containers too: check for them explicitly so they clone as arrays, not as objects with numeric keys.
Approach, complexity & discussion — open after you solve
The approach
Four stages, and the third one invalidates almost every naive implementation. Stage 1 is a shallow copy. Stage 2 recurses into nested objects and arrays. Stage 3 introduces a cycle, at which point unguarded recursion overflows the stack. Stage 4 asks for something subtler: two properties that pointed at the same object before must still point at the same object after.
Both stages 3 and 4 fall out of one idea — a map from every original object to its clone, consulted before you recurse. Seen it before? Return the existing clone. That single lookup terminates cycles and preserves shared identity at the same time, which is why an implementation that adds a bare visited set for cycle-breaking still fails stage 4.
Complexity
O(n) in the number of nodes and edges; O(n) extra space for the identity map.
Common mistakes
- Using a plain set of visited objects to stop the recursion, which breaks the cycle but returns the wrong shape — you need the map from original to clone, not a membership test.
- Cloning shared sub-objects twice, so
out.a === out.bis false whensrc.a === src.bwas true. - Forgetting that arrays are objects too, and cloning them into plain objects with numeric keys.
- Treating
nullas an object and recursing into it — the classictypeof null === "object"trap in JavaScript.
Where this shows up
Every serialiser, state-management library and undo stack meets this. The reason it is a good incremental round is that each stage is a reasonable next sentence from an interviewer, and the third one genuinely breaks the obvious design — so it tests whether you refactor calmly or patch around the symptom. Narrating "a visited set fixes the crash but loses shared identity, so I want a map instead" is the whole signal.
Explore the topic
See this challenge alongside everything else on the same subject — handbooks, system designs, algorithms and tools, in one place.