skip to content

Immutability

7 roadmaps21 questions

Values that never change after construction, and the machinery that keeps that affordable: persistent structures, structural sharing, copy-on-write. Interviewers chase the shallow-versus-deep trap.

on this pageshow

explore

questions

21

A document editor keeps past versions in a persistent structure - after an edit, what can an old reference still do?

level: juniorimportance: must knowfreq 58%

answer

  1. old versions do not die
  2. ephemeral is the opposite word
  3. the update returns something
  4. not storage, versions in memory
  5. previous handle still fully readable

basics

~20 s

A persistent structure never destroys the version an update was applied to. The edit returns a new version, and a reference taken earlier still reads exactly the document it read before, with no copy having been taken.

solid answer

~40 s

Persistent means every version stays valid after an update. The edit is a function from version to version: it returns `v2` and leaves `v1` completely usable, so the undo stack, a background spell-checker mid-pass and a diff view can all keep reading `v1` while editing continues on `v2`. Nothing was snapshotted and nothing was invalidated - the old handle is the real document, not a defensive copy of it. The contrast is an *ephemeral* structure, the ordinary mutable kind, which holds one state that each write overwrites, so anything wanting the previous text had to copy it beforehand. Persistence here means versions stay addressable in memory; it says nothing about writing to storage.

code

pseudocode · 11 lines
pseudocode
let v1 = document with lines ["alpha", "beta"]

let v2 = replaceLine(v1, 1, "BETA")   // returns a NEW version

print lineAt(v1, 1)     // "beta"  - v1 was not touched
print lineAt(v2, 1)     // "BETA"

undoStack.push(v1)      // v1 is a usable document, not a saved copy

let v3 = replaceLine(v2, 0, "ALPHA")
print lineAt(v1, 0)     // still "alpha"

go deeper

for a junior

Recall the one-line guarantee: an update returns a new version and the old one stays readable. Always bind the returned value - the version you passed in is intentionally unchanged.

for a middle

Explain the contrast with an ephemeral structure and why old versions are not copies: the update rewrites only what it changed and both roots reach everything else. Name the three distinct promises - immutable value, persistent structure, read-only handle.

for a senior

Show where the guarantee earns its keep in a running system: snapshot reads with no lock and no copy, handing a version to another worker safely, undo as a list of roots. Then name the bill - every retained version retains what it can reach.

for a principal

Frame it as a system property, not a collection choice: adopting versions-as-values changes how state is published, how history is bounded and how teams reason about concurrent readers. Decide where the boundary of that model sits before the memory profile decides for you.

## What the word promises A data structure is **persistent** when an update leaves the version it was applied to intact and still usable. The structure persistence is defined against is called **ephemeral**: it holds exactly one state, and every write destroys the state before it. The word is unfortunate, because it has nothing to do with durable storage - nothing here is written to a file. It means **versions stay addressable in memory**. Take the setting concretely. An editor holds document version `v1`. A keystroke produces `v2`. In an ephemeral buffer the keystroke rewrites the text in place, so whatever wanted the previous state had to have copied it first - that is exactly what a hand-rolled undo stack is. In a persistent document the edit *returns* `v2`, and `v1` remains a complete, readable, queryable document that anything still holding it may keep using. ## What an update actually hands back Three consequences follow directly from the definition: - **The update is a function from version to version.** Its result is the new version. If you ignore the return value, nothing you can observe has changed - a classic beginner bug against this kind of structure. - **The old handle is not a snapshot.** No copy was taken on its behalf. It is the same version object it always was; the update simply did not touch it. - **Nothing is invalidated.** There is no equivalent of an iterator that blows up because someone wrote to the collection underneath it, because nobody can write to a version at all. ## Persistent, immutable, read-only: three different promises These three get used interchangeably and mean different things. | term | what it actually constrains | |---|---| | immutable value | this value's own fields never change after it is constructed | | persistent structure | an update yields a new version and every earlier version stays valid | | read-only view | the holder of *this* handle cannot write through it; someone else still might | A persistent structure is normally built out of immutable nodes, so the two travel together, but they answer different questions: immutability is about one value, persistence is about the *family of versions* an update generates. A read-only handle over an ephemeral structure gives you neither - the data can still change under you, you are just not the one changing it. ## Why keeping the old version is affordable The naive way to keep every version is to copy the whole document per keystroke, which is quadratic in the session and obviously unusable. Real persistent structures avoid it by rewriting only the nodes on the route from the root to the slot that changed and pointing the new root at them; every part the edit did not touch is reachable from both roots at once. That is why holding `v1` and `v2` together costs far less than two documents - though it is not free, and a structure small enough that its whole body sits on the changed path really is copied end to end. ## What the guarantee buys in practice - **Undo and redo become trivial.** The history is a list of roots; undo is picking an earlier one, not replaying inverse operations. - **Snapshot reads need no lock and no copy.** A long-running word count can walk `v1` to completion while the user types into `v9`. - **Handing a version to another worker is safe by construction.** There is nobody who could mutate it while the worker reads. - **Comparing two versions is a normal traversal**, because both versions genuinely exist. ## What it costs, honestly - **An update is more than a memory store.** It allocates the nodes along one path and touches scattered memory, where an in-place write touches one slot. - **A retained version retains its nodes.** Every root you still hold keeps everything it can reach alive; an unbounded history is an unbounded memory bill. - **The guarantee is only as deep as the structure.** If a version's slots hold handles to something mutable, the version is fixed but what it points at need not be. ## How to check the claim When someone says a structure is persistent, three questions settle it: *what does an update return?* *Can I still read the handle I had before it?* *Can I still update that older handle?* A structure that answers the first two but not the third is persistent in the weaker, partial sense - all versions readable, only the newest one extendable - which is often exactly what an editor needs and sometimes not enough.

  • A developer calls the update and then reads the same handle they passed in, and sees no change. What did they get wrong?
    They treated the update as a command when it is a function. The update produces a new version and returns it; the version passed in is deliberately untouched. The fix is to bind and use the returned version - ignoring the result of an update against a persistent structure is always a bug, never a no-op you can shrug at.
  • Does calling a structure persistent tell you anything about what its elements can do?
    No. Persistence constrains the structure's own versions: each one stays valid after an update. If a version's slots hold handles to objects that can still be changed, the version's shape is fixed while the data reachable through it is not. That distinction is separate from persistence and has to be checked on its own.
  • Why is 'persistent' a confusing name for this property?
    Because the same word is used elsewhere for data that survives a process restart on durable storage. Here it means only that earlier versions survive an update in memory. A persistent structure disappears with the process like any other in-memory value; the persistence is across *versions*, not across *runs*.

A bound ledger written only on fresh pages: you never scribble over an old entry, so a bookmark placed last week still lands on exactly what it named, and the newest page is simply further on.

saying these in an interview costs you the question

  • Thinks persistent means saved to disk between runs
  • Says the old reference now sees the updated data
  • Assumes the update mutated in place and returned nothing useful
  • Believes keeping the old version required a full copy first
  • Cannot separate a read-only handle from an unchangeable version
  • Assumes retaining a version costs nothing
open as a page

A price list's tier-row field is never reassigned, yet a reader sees a row's amount change — why?

level: juniorimportance: must knowfreq 72%

basics

~20 s

Fixing a field fixes the binding, not the object it points at. The tier rows are separate objects; anyone holding a reference to one can write its amount in place, without ever touching the price list's field.

open as a page

Every request handler reads one shared routing-table value that is never modified after it is built; why does no handler need a lock?

level: juniorimportance: must knowfreq 60%

basics

~20 s

A value that never changes has no intermediate state to hide, so concurrent readers have nothing to exclude each other from. Locks guard transitions, and this value makes exactly one: from unbuilt to finished, before anybody can see it.

open as a page

An immutable tree-shaped value gets one leaf replaced — why is the new version not a full copy?

level: juniorimportance: must knowfreq 64%

basics

~20 s

Only the nodes along the route from the root to the changed leaf are rebuilt; every subtree the change never touched is pointed at by both versions. The copy is one path deep, not one tree wide.

open as a page

A cart line is immutable — how do you produce one with a new quantity, and what happens to the original?

level: juniorimportance: must knowfreq 70%

basics

~10 s

You build a new line that copies every field except quantity, which takes the new value. The original object is untouched, so any code already holding it keeps seeing the old quantity.

open as a page

For a published price list to be deeply immutable, what must be true of every object reachable from it?

level: middleimportance: must knowfreq 60%

basics

~20 s

Deep immutability is a closure property: follow every reference out of the price list, and out of those objects in turn, and each object found must be unwritable by anyone at all — including whoever built the value and still holds a reference into it.

open as a page

If the shared routing table is immutable and needs no lock, which part of that design still needs coordination between publishers?

level: middleimportance: must knowfreq 58%

basics

~20 s

The mutable reference that names the current table. It has to hand over in one indivisible step, and two publishers that each derive a new table from the same old one will lose one of the changes unless publication is serialised.

open as a page

When path copying replaces one leaf of an immutable tree, exactly which nodes must be freshly allocated?

level: middleimportance: must knowfreq 54%

basics

~20 s

The replacement leaf, plus a new copy of every node on the route from the root down to it, including a new root. That is depth-many nodes. Every node off the route is reused as-is.

open as a page

A loop applies 1,000 line edits to an immutable cart by copying the whole cart each time — what does that cost?

level: middleimportance: must knowfreq 58%

basics

~20 s

Each edit builds a whole new cart container, so one edit costs work proportional to the number of lines, and 1,000 edits cost roughly 1,000 times that plus 1,000 allocations — a throughput cost, not a memory-footprint one.

open as a page

Why is a persistent map's logarithmic update usually acceptable against a mutable structure's constant-time in-place write?

level: middleimportance: should knowfreq 46%

basics

~20 s

Depth, not size, sets the cost. A wide branching factor keeps a map of millions only about four levels deep, so an update rewrites a handful of small nodes - a bounded constant in practice, for which you get every earlier version still valid.

open as a page

How does a wider branching factor change what one structurally shared update has to copy?

level: middleimportance: should knowfreq 40%

basics

~10 s

Wider nodes make the tree shallower, so fewer nodes are rebuilt per update — but each rebuilt node now carries more child references to copy. Fewer allocations, more references copied inside each.

open as a page

Rebuilding an immutable cart, why batch many edits into a temporary mutable buffer and freeze it once at the end?

level: middleimportance: should knowfreq 50%

basics

~20 s

Because the intermediate carts nobody can see do not have to exist. Edits go into a private buffer in place, and one immutable value is produced at the end — one allocation instead of one per edit.

open as a page

In an editor that keeps every past document version reachable, what is actually retained in memory as edits accumulate?

level: seniorimportance: should knowfreq 38%

basics

~20 s

Everything any live version root can still reach. Because versions overlap heavily, the total is the common base plus the nodes each update replaced - not versions times document size - and a node is freed only when no live root reaches it.

open as a page

A price-list type documented as immutable returns its live tier-row container from an accessor — which promises to callers are now false?

level: seniorimportance: should knowfreq 45%

basics

~20 s

Three promises collapse at once: that a check made at construction still holds at read time, that two reads agree so a derived result can be cached, and that the value can be passed around and treated as stable. One writable path falsifies all of them.

open as a page

What does deep-freezing every object reachable from a published price list cost as that graph grows?

level: seniorimportance: should knowfreq 38%

basics

~20 s

It costs a full walk of the reachable graph on every publication: work proportional to the number of reachable objects, not to the size of the edit. Parts nothing touched are re-walked, and some objects cannot be made unwritable from outside at all.

open as a page

A handler reads the shared routing reference once at request start and a new table is published mid-request; what has that handler gained and lost?

level: seniorimportance: should knowfreq 45%

basics

~20 s

It gained a stable snapshot: every decision in that request is taken against one version, with no lock and no risk of routes shifting between two lookups. It lost freshness, acting on a table it already knows may be superseded.

open as a page

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%

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.

open as a page

After freezing a mutable buffer into an immutable cart, what goes wrong if a reference to that buffer survives?

level: seniorimportance: should knowfreq 38%

basics

~20 s

If the freeze handed over the buffer's storage instead of copying it, a surviving handle can still write that storage — so a cart callers were told could never change does change, and every conclusion drawn from its immutability becomes unsound.

open as a page

In a versioned document structure, what distinguishes full persistence from partial persistence for a user editing an old version?

level: middleimportance: nice to knowfreq 24%

basics

~20 s

Partial persistence lets every version be read but only the newest be updated, so history is a straight line. Full persistence lets any version be updated too, so editing an old one forks history into a tree of versions.

open as a page

Why can two versions of a structurally shared tree be compared without walking every node?

level: middleimportance: nice to knowfreq 28%

basics

~10 s

Wherever both versions hold the same node, everything below it is unchanged by construction, so the walk stops there. Only rebuilt routes differ, so the comparison costs the size of the change.

open as a page

The routing table and its matching weight map are immutable but sit behind separate references; what can a reader observe?

level: seniorimportance: nice to knowfreq 30%

basics

~20 s

A pair that was never published together: the new table with the previous weights, or the reverse. Each value is whole, but atomicity follows the reference, so two references mean two independent handovers and a window between them.

open as a page