Build fluency in the vocabulary of preserving every version of a data structure efficiently via structural sharing.
0 / 5 completed
1 / 5
A teammate describes a data structure where every update produces a new version while all previous versions remain fully accessible and unmodified, typically by sharing most of the internal structure between versions instead of copying everything. What is this called?
A persistent data structure is exactly this: every update returns a new version while all prior versions remain fully accessible and unmodified, and this is made efficient by sharing most of the unchanged internal structure between versions rather than copying the entire structure on every update. A hash collision is an unrelated hash-table concept about two keys sharing a bucket. This preserve-every-version-via-sharing approach is exactly why persistent data structures underlie undo history and functional-language immutable collections.
2 / 5
During a design review, the team adopts a persistent tree structure for an editor's undo history, specifically so that reverting to any prior document version never requires deep-copying the entire document tree. Which capability does this provide?
A persistent tree here provides efficient access to every prior version via structural sharing, since only the changed path of the tree is rebuilt while the rest is shared with the previous version. Deep-copying the whole document tree on every edit would make undo history expensive in both time and memory as the document grows. This share-the-unchanged-parts behavior is exactly why persistent data structures are favored for undo history and version-tracked collections.
3 / 5
In a code review, a dev notices an undo-history feature deep-copies the entire document tree on every single keystroke, instead of using a persistent tree that shares unchanged branches between versions. What does this represent?
This is a missed persistent-data-structure opportunity, since sharing unchanged branches between versions would avoid the cost of deep-copying the entire tree on every keystroke. A cache eviction policy is an unrelated concept about discarded cache entries. This deep-copy-per-keystroke pattern is exactly the kind of wasted memory and time a reviewer flags once undo history for a large document is the goal.
4 / 5
An incident report shows the editor's memory usage grew unbounded and typing became sluggish because a full deep copy of the document tree was stored on every keystroke for undo purposes. What practice would prevent this?
Switching the undo history to a persistent tree structure lets each keystroke's version share unchanged branches with the previous version instead of copying the whole tree. Continuing to deep-copy the entire document tree on every keystroke regardless of how much memory or time it consumes is exactly what caused the sluggishness and memory growth described in this incident. This structural-sharing approach is the standard fix once full deep copies per update are confirmed to be too expensive.
5 / 5
During a PR review, a teammate asks why the team reaches for a persistent data structure instead of a plain mutable structure with manual snapshotting, given that mutable structures are usually simpler and faster for single-version use. What is the reasoning?
A persistent data structure trades a small overhead per update for cheap access to every prior version via structural sharing, while a mutable structure with manual snapshotting is simpler for a single version but requires expensive full copies to preserve history. This is exactly why persistent data structures are favored when many historical versions must stay cheaply accessible, while plain mutable structures remain acceptable when only the current version ever matters.