Prompt and context
Implement an integer array structure with history. Each update changes one position, and a query may ask for a closed-interval sum in any old version. Old versions must remain immutable. Explain coordinate bounds, time and space complexity, branching versions, and tests.
This is a hard data-structure question about divide-and-conquer, structural sharing, immutable updates, boundaries, and complexity proofs. Assume a fixed array length, point assignment updates, and closed-interval range sums [l, r]. Range updates, deletion, or merging versions are separate extensions and should be called out before being implemented.
What the interviewer is testing
The interviewer wants you to clarify that persistence keeps old roots queryable; it does not copy the whole tree for every update. A strong implementation creates new nodes along the update path, reuses untouched subtrees, and stores one root per version. It also states the interval convention, empty-query behavior, version numbering, negative values, bounds, and the space limit.
Questions to clarify first
- Is the array length and coordinate universe fixed, or can coordinates be compressed first?
- Is an update assignment or an increment, and can the same position be updated repeatedly?
- Are ranges closed or half-open, and what should an empty range return?
- Can a version branch from any old root, or only append from the newest version?
- Is thread safety, disk persistence, or cross-process sharing required?
- Do we need exact integer sums, overflow checks, or big integers?
- What are the version and total-operation limits?
30-second answer framework
“I would represent each version by the root of an immutable segment tree. A point update copies O(log n) nodes from root to leaf, shares every untouched sibling subtree, and a query descends from the requested root, returning a node sum for full coverage. An array of roots permits branching from any old version. Building is O(n); each update and query is O(log n); total space is the initial tree plus O(log n) new nodes per update. I would test forks, boundaries, negative values, and random differential cases.”
Step-by-step answer
State the invariant first: a node covers a specific closed interval [lo, hi], sum is the sum of that interval in its version, a leaf covers one position, an internal sum equals the sum of its children, and a node is never mutated after creation. Each version stores one root pointer.
For array indices 0..n-1, build recursively. If the input uses sparse, large integer coordinates, collect possible coordinates and compress them before building; do not materialize a huge coordinate universe.
The following pseudocode uses assignment updates and closed-interval queries:
Node { left, right, sum }
build(lo, hi, values):
if lo == hi: return Node(null, null, values[lo])
mid = floor((lo + hi) / 2)
left = build(lo, mid, values)
right = build(mid + 1, hi, values)
return Node(left, right, left.sum + right.sum)
set(node, lo, hi, index, value):
if lo == hi: return Node(null, null, value)
mid = floor((lo + hi) / 2)
if index <= mid:
nextLeft = set(node.left, lo, mid, index, value)
nextRight = node.right
else:
nextLeft = node.left
nextRight = set(node.right, mid + 1, hi, index, value)
return Node(nextLeft, nextRight, nextLeft.sum + nextRight.sum)
sum(node, lo, hi, ql, qr):
if qr < lo or hi < ql: return 0
if ql <= lo and hi <= qr: return node.sum
mid = floor((lo + hi) / 2)
return sum(node.left, lo, mid, ql, qr)
+ sum(node.right, mid + 1, hi, ql, qr)roots[0] stores the initial tree. To update position i from version base, create roots[next] = set(roots[base], 0, n - 1, i, value). The version graph is a directed acyclic shared structure referenced by roots, not a linear history chain. Branching means choosing any old root as the update input.
Handle boundaries explicitly: for n == 0, do not create a root; out-of-range indices and ql > qr should return a structured error or follow the stated contract; clipping a query must not silently hide a caller error. Avoid lo + hi overflow by computing lo + floor((hi - lo) / 2) when integer bounds can be large.
Initial construction uses O(n) nodes and time. A point update copies one root-to-leaf path, so it creates O(log n) nodes; a range query visits O(log n) canonical segments and takes O(log n) time. After u updates, total space is O(n + u log n), not O(nu). Range assignment or addition can also use path copying, but lazy tags, node combinations, and space bounds change.
Immutability is the correctness boundary. Never modify an old node's sum or child pointer during an update. Garbage collection or reference counting can reclaim nodes; manual reclamation must know which version roots remain live, because deleting one version cannot free nodes still shared by another.
If only the latest version matters, a normal segment tree is simpler. Persistence pays for historical queries, rollback, branching experiments, or time travel. For fully offline operations, an offline prefix or sweep-line method may be simpler; connect the data-structure choice to the query workload.
Start tests with tiny arrays. After each update, copy a plain array and compare random versions and ranges with the persistent structure. Cover branching from version 0, repeated updates to one position, negatives, a single element, full ranges, single points, empty ranges, and both boundaries. Also check sharing: after updating one position, the untouched subtree should keep the same object identity.
Test immutability directly. Save all old-version query results, perform several branching updates, and query the old roots again; any change means an old node was mutated. For large workloads, count allocated nodes and confirm growth near initial O(n) plus O(log n) per update rather than accidental whole-tree copies.
High-quality sample answer
“I will assume a fixed-length array, point assignment updates, closed-interval sums, and branching from any old version. Each node covers [lo, hi] and stores its sum; nodes are immutable after construction. roots[v] stores the root for version v.
Build recursively. On update, copy the path to the target leaf: create a new child on the target side, reuse the old pointer on the other side, and create each new parent from its children’s sums. Query from the requested root; return zero for no overlap, the node sum for full coverage, and recurse otherwise.
Build is O(n) time and space. Each update creates O(log n) nodes, and both update and query are O(log n); after u updates, total space is O(n + u log n). Old roots still point to old nodes, so historical versions cannot be polluted. Compress a large coordinate universe first; for range updates, re-evaluate lazy tags and space.
I would test forks from version 0, repeated updates, negatives, empty ranges, and every boundary against a plain-array oracle. I would verify untouched subtrees are shared and old queries stay unchanged after new updates. If only the newest value is needed, I would use a regular segment tree and pay for persistence only when history or rollback is a real requirement.”
Common mistakes
- Copy the whole tree → every update becomes O(n) space → copy only the root-to-leaf path.
- Mutate an old node and save a new root → every old version sharing it changes → keep nodes immutable.
- Treat versions as a chain → you cannot experiment or roll back from an arbitrary root → let the root array branch.
- Leave the interval convention implicit → closed and half-open ranges create boundary bugs → fix one convention in invariants and signatures.
- Materialize huge coordinates → the universe may dwarf the actual points → compress coordinates or use dynamic nodes.
- Claim O(n) total space → each update adds path nodes → state O(n + u log n).
- Recursively free nodes when deleting a version → another version may still share them → use reference counting or garbage collection.
Follow-up questions and answers
Follow-up 1: Does the structure still work for range addition?
Path-copy the nodes touched by the update and copy every relevant path. If lazy tags are used, the tag belongs to a new node and must never be written into a shared node. New-node count may range from O(log n) to O(log n plus covered nodes), so give bounds for the actual implementation instead of reusing the point-update claim.
Follow-up 2: How would you query the difference between two versions?
Traverse both roots together. If the node pointers are identical, that subtree is unchanged and can be skipped. Otherwise descend or compute an aggregate difference. Reporting every changed position also depends on the output size.
Follow-up 3: Why not copy the array and build a prefix sum each time?
Copying the array costs O(n) time and space per update. With few versions and a small array, that simpler method may win; persistence trades O(log n) new space for many versions, online historical queries, and local updates.
Follow-up 4: How do you persist version roots to disk?
Give nodes stable IDs, store child IDs instead of memory pointers, and persist a version-to-root table. Use append or copy-on-write and ensure new nodes are durable before publishing the root. On recovery, validate references and the root table; never serialize raw memory addresses.
Follow-up 5: How do you prove an old version is not polluted?
Induct over updates: only new nodes are created, no old node field changes, and the new tree references old untouched subtrees plus a new path. Therefore the nodes reachable from an old root and their values remain unchanged. Random branching differential tests validate the invariant in practice.