skip to content

An hourly snapshot service stores immutable trees, and each new version's memory grows with the whole tree — what did its update code get wrong?

level: seniorimportance: should knowfreq 36%

answer

  1. the growth curve names the defect
  2. depth-shaped cost, not size-shaped
  3. copied children, not copied references
  4. compare untouched subtrees by identity
  5. assert node count per update in a test

basics

~20 s

It is duplicating subtrees it only walked past instead of carrying their references over, so every update is a deep copy wearing path copying's shape. Cost per version tracks the element count rather than the route's depth.

solid answer

~40 s

The symptom names the defect: if per-version memory grows with the size of the tree, nothing is being shared. A correct update rebuilds one route and puts the old child *references* into the new nodes; a broken one recursively copies the children it did not need to change, which makes the first level alone duplicate nearly the whole structure. Confirm it by taking a subtree that provably did not change between two consecutive versions and comparing the two versions' nodes **by reference**, not by value — sharing means the same node, not an equal one. Then read the update routine for a recursive copy that descends into children off the route. The fix is a shallow copy of the one node's slot array with a single slot swapped.

code

pseudocode · 11 lines
pseudocode
function update(node, route, i, value):        // BROKEN
    if i == length(route):
        return value

    newChildren = []
    for each child in node.children:
        newChildren.append(deepCopy(child))    // duplicates untouched subtrees

    slot = route[i]
    newChildren[slot] = update(node.children[slot], route, i + 1, value)
    return Node(newChildren)

go deeper

for a junior

Learn the expected cost first: one update should add memory for one route's worth of nodes. Memory that grows with the whole structure means nothing is being reused.

for a middle

Point at the line that decides — the update must copy child references, not children — and say what the broken version costs at the first level alone.

for a senior

Diagnose from the growth curve before reading code, confirm with a reference-identity comparison across two versions, and fix the routine rather than the symptom.

for a principal

Decide what standing guard the codebase gets: an identity-based sharing test and a node-count budget per update, so a complexity regression fails a check instead of surfacing as a memory graph.

This is the failure that makes an immutable design look like proof that immutability is unaffordable — and the cause is almost always a few lines of the update routine, not the paradigm. ## Reading the symptom The cost model tells you what each version should cost: - **Correct sharing:** memory added per version is proportional to the route's length times the node width, so it grows with the *depth* — barely at all as the data grows. - **What was observed:** memory added per version grows with the *size of the tree*. Those are different functions of `n`, so the observation is not a tuning problem or a collector problem. Something is duplicating nodes the update never needed to touch. ## The usual cause The bug is an update routine that, at each level of the route, rebuilds the whole child list by **copying each child** rather than copying each **reference to** a child. One word of difference in the code; a different complexity class in production. At the first level alone, copying every child of the root duplicates nearly the entire structure, so the update is O(n) in both time and memory instead of proportional to the depth. Related variants that produce the same curve: - A "safety" deep copy taken at the boundary before the update starts, so the update shares perfectly — with a duplicate nobody needed. - A rebuild that reconstructs a node from its *contents* (re-reading and re-wrapping each child) instead of from its existing child references. - A serialize-then-deserialize round trip used to produce the new version, which by construction shares nothing. ## How to confirm it in a running system 1. **Compare by reference.** Take a subtree that certainly did not change between two consecutive versions and ask whether the two versions hold *the same node* or merely equal ones. Sharing is a statement about node identity; equality proves nothing here. 2. **Plot memory per version against depth and against size.** Two versions of a structure twice as large should add about the same memory per update if sharing works, and about twice as much if it does not. 3. **Count the nodes an update builds.** Instrument the constructor; a correct single-position update builds depth-many nodes plus the new value. Anything proportional to the element count is the defect. 4. **Read the recursion.** Look for a recursive copy applied to children that are not on the route. The correct code touches one slot per level. | Signal | Sharing works | Sharing is broken | |---|---|---| | Untouched subtree across versions | the same node | equal but distinct nodes | | Memory added per version | tracks the depth | tracks the element count | | Nodes built per update | depth-many, plus the value | proportional to the size | | Update time as data grows | nearly flat | grows with the data | ## The fix, and the discipline that prevents it Rebuild only the nodes on the route; fill every other slot with the reference the old node held. Then keep two habits: - **A test that asserts identity, not equality.** Update one position, then assert that an untouched subtree in the new version *is the same node* as in the old. This is the only test that can fail when sharing silently stops working, and a value-equality test will happily pass against a deep copy. - **A cost test that grows the data.** Assert that nodes built per update does not grow with the element count. It turns a complexity regression into a failing check rather than a memory graph someone notices months later. ## The judgment to show The interesting part of the answer is that you diagnosed it from the shape of the growth curve before reading any code: per-version memory that tracks the element count is a statement that nothing is being reused, and that narrows the search to the one routine that decides what to reuse. Saying "immutable data is expensive" instead is the answer that ends the conversation — the mechanism's whole claim is that the update is depth-shaped, so a size-shaped cost means the mechanism is not running.

  • What single check tells you whether sharing is happening at all?
    Take a subtree that did not change between two versions and compare the two versions' nodes by reference. Sharing means it is the same node. An equality check cannot distinguish sharing from a faithful deep copy, so it never fails on this defect.
  • What should per-version memory track in a correct implementation?
    The route's length times the node width — so it grows with the depth, which is the logarithm of the element count. Doubling the data should leave the per-update cost almost unchanged.
  • How would you keep the defect from coming back?
    Two tests: one asserting that an untouched subtree in the new version is the identical node from the old version, and one asserting that the number of nodes built per update does not grow as the data grows.

saying these in an interview costs you the question

  • Concludes that immutable data structures are simply too expensive
  • Checks sharing with a value-equality assertion, which a deep copy also passes
  • Takes a defensive deep copy before the update to be safe
  • Rebuilds a node from its children's contents rather than their references
  • Blames memory growth on collection tuning rather than on a size-shaped update
  • Assumes any structure described as immutable must already share