Persistent Segment Tree — Interview Preparation¶

Format: 45 tiered questions (Junior → Middle → Senior → Professional) with model-answer focus, followed by a full coding challenge — range k-th smallest in Go, Java, and Python. Cross-links: ordinary segment tree, Fenwick tree, wavelet tree.

How to Use This File¶

Each question lists the answer focus an interviewer wants to hear. Practice saying the answer out loud in 60–120 seconds. The coding challenge at the end is the canonical "k-th smallest in a range" problem (SPOJ MKTHNUM / Codeforces flavor) — the single most common way this structure is tested.

Junior Questions (What & How)¶

Sample full answer — Q3 (path copying): "When I update one leaf, only that leaf and its ancestors change their aggregate — everything hanging off the side of the path is untouched. So I clone just the nodes on the root-to-leaf path (about log n of them), point the cloned nodes' off-path child at the old subtree (sharing it), and return the new root. The old root still points at the old path, so the previous version is fully intact. Cost: O(log n) time and O(log n) new nodes per version."

Middle Questions (Why & When)¶

Sample full answer — Q13 (k-th): "I compress the values to ranks 0..D−1. I build a count segment tree over the value axis where each node stores how many elements fall in its value range. Version i is version i−1 plus one at the bucket of a[i], so version i is the histogram of the first i elements. To answer (l,r,k), I note the histogram of a[l..r] is version[r] − version[l−1] bucket by bucket. I descend: at each node leftCount = version[r].left.cnt − version[l−1].left.cnt. If k ≤ leftCount the answer is in the smaller-value half, recurse left; otherwise subtract leftCount from k and go right. At the leaf I have the rank; map back to the value. Each query is one O(log n) descent over two roots."

Senior Questions (Scale & Systems)¶

Sample full answer — Q28 (arena): "Heap-allocating one object per node is the killer: millions of tiny objects thrash the allocator and the GC has to scan every pointer. I switch to a node arena — three parallel arrays cnt[], lc[], rc[] where a node is an int32 index and children are int32 indices, with index 0 as the empty sentinel. Allocation is a bump (free++). The GC now sees one big pointer-free slice instead of millions of objects, so pause times drop dramatically, and the packed layout (~12 bytes/node) roughly halves memory versus heap pointers."

Professional Questions (Proofs & Theory)¶

Sample full answer — Q38 (allocation count proof): "Let N(w) be allocations on a range of width w. Base: a leaf (w=1) allocates 1. Inductively, an internal node allocates itself (1) and recurses into exactly one child — the side containing the index — sharing the other. So N(w)=1+N(w') with w'≤⌈w/2⌉. The width halves each level, so the depth is ⌈log₂ n⌉, giving N(n)=⌈log₂ n⌉+1. It's also necessary: every node on the path covers the updated index, so its aggregate changes, and since nodes are immutable we can't edit the old one — each must be freshly allocated. Hence exactly ⌈log₂ n⌉+1."

Extended Model Answers (Whiteboard-Ready)¶

These are the answers most likely to make or break a loop — practice delivering them with a small drawing.

Q4 expanded — "Exactly how many new nodes per update, and why exactly that?" "Draw the tree. An update to index i walks one root-to-leaf path. At each internal node on the path I must create a new node because its aggregate (which covers i) changes, and the structure is immutable so I can't edit the old one. The off-path child pointer is copied verbatim — that's the sharing. The path has one node per level, and the height is ⌈log₂ n⌉, so I create ⌈log₂ n⌉ internal nodes plus the leaf = ⌈log₂ n⌉ + 1. Not fewer (each path node truly changes), not more (only one child is recursed into). For n = 8 that's exactly 4, every time."

Q14 expanded — "Convince me the l−1 subtraction is correct, not just a trick." "Counts are linear in the version index: version[i] differs from version[i−1] by exactly +1 at the bucket of a[i]. So for any node u, cnt(u, r) − cnt(u, l−1) telescopes to Σ_{j=l}^{r} [rank(a_j) ∈ range(u)] — the number of elements of a[l..r] in that node's value range. It holds for every node at once, so when I descend I can compute the left-child count of the sub-array as right.left.cnt − left.left.cnt at each level. Using version[l] instead would drop element a[l]."

Q27 expanded — "Walk me through the memory math for a million versions." "Build version 0 is ~2n nodes. Each update path-copies ⌈log₂ n⌉ + 1 nodes. After m updates: 2n + m·(log n + 1) = Θ(n + m log n). At n = m = 10^6, log n ≈ 20, so ~2·10^6 + 2·10^7 ≈ 2.2·10^7 nodes. In an arena at 12 bytes/node that's ~265 MB. The naive 'copy the whole tree each time' would be m·2n = 2·10^12 nodes — about n/log n ≈ 50,000× more, completely infeasible. With lazy-empty version 0 the 2n term vanishes and it's Θ(m log n)."

Q40 expanded — "Prove the k-th descent terminates with the right answer." "Invariant: at each call the k-th smallest of a[l..r] whose value-rank is in [lo,hi] equals the global k-th. Initially [lo,hi] is the whole axis so it trivially holds. At a node, leftCount = number of a[l..r] elements in the left value-half. If k ≤ leftCount, the k-th is among the smaller values → recurse left, same k. Else the first leftCount are all smaller, so skip them: recurse right with k − leftCount. Each step halves the value range, terminating at a leaf in ⌈log₂ D⌉ steps; the leaf's rank maps to the answer. Both 1 ≤ k ≤ count preconditions are maintained, so we never run off the end."

Scenario / Design Questions¶

Sample full answer — S1: "I'd index a segment tree by compressed score buckets where each node counts players in its score range; rank(X) is a prefix-count query in O(log n). For 'as of last season,' I freeze one persistent version at each season boundary — that root is immutable, so historical-rank reads are lock-free and scale across replicas with zero coordination. To avoid millions of versions, I keep a mutable ephemeral tree for 'right now' and only materialize a persistent version per snapshot window. Memory is O(n + S·log n) for S retained snapshots — tiny. This is essentially MVCC: a single writer publishes new roots, readers snapshot."

Common Wrong Answers (and the Fix)¶

Rapid-Fire Conceptual Checks¶

Coding Challenge — Range K-th Smallest¶

Problem. Given a static array a[1..n] and q queries (l, r, k) (1-indexed, 1 ≤ k ≤ r−l+1), return the k-th smallest value among a[l..r] for each query. Approach. Coordinate-compress values; build n+1 prefix count-versions of a persistent segment tree over the value axis; answer each query by descending version[r] and version[l−1] in lockstep using the left-count, in O(log n). Complexity. Build O(n log n), each query O(log n), memory O(n log n).

Sample. a = [3, 1, 4, 1, 5], queries (2,4,2) (1,5,3) (1,5,1) (3,5,2) → 1 3 1 4.

Go¶

package main

import (
    "bufio"
    "fmt"
    "os"
    "sort"
)

type Node struct {
    cnt         int
    left, right *Node
}

var D int

func build(lo, hi int) *Node {
    if lo == hi {
        return &Node{}
    }
    mid := (lo + hi) / 2
    return &Node{left: build(lo, mid), right: build(mid+1, hi)}
}

func insert(prev *Node, lo, hi, g int) *Node {
    if lo == hi {
        return &Node{cnt: prev.cnt + 1}
    }
    mid := (lo + hi) / 2
    if g <= mid {
        l := insert(prev.left, lo, mid, g)
        return &Node{cnt: l.cnt + prev.right.cnt, left: l, right: prev.right}
    }
    r := insert(prev.right, mid+1, hi, g)
    return &Node{cnt: prev.left.cnt + r.cnt, left: prev.left, right: r}
}

func kth(l, r *Node, lo, hi, k int) int {
    if lo == hi {
        return lo
    }
    mid := (lo + hi) / 2
    leftCnt := r.left.cnt - l.left.cnt
    if k <= leftCnt {
        return kth(l.left, r.left, lo, mid, k)
    }
    return kth(l.right, r.right, mid+1, hi, k-leftCnt)
}

func main() {
    reader := bufio.NewReader(os.Stdin)
    writer := bufio.NewWriter(os.Stdout)
    defer writer.Flush()

    a := []int{3, 1, 4, 1, 5} // (replace with input parsing in a judge)
    n := len(a)

    sorted := append([]int(nil), a...)
    sort.Ints(sorted)
    uniq := sorted[:0]
    for i, v := range sorted {
        if i == 0 || v != sorted[i-1] {
            uniq = append(uniq, v)
        }
    }
    D = len(uniq)
    rank := func(v int) int { return sort.SearchInts(uniq, v) }

    roots := make([]*Node, n+1)
    roots[0] = build(0, D-1)
    for i := 1; i <= n; i++ {
        roots[i] = insert(roots[i-1], 0, D-1, rank(a[i-1]))
    }

    queries := [][3]int{{2, 4, 2}, {1, 5, 3}, {1, 5, 1}, {3, 5, 2}}
    for _, q := range queries {
        l, r, k := q[0], q[1], q[2]
        g := kth(roots[l-1], roots[r], 0, D-1, k)
        fmt.Fprintf(writer, "%d\n", uniq[g])
    }
    // prints: 1 3 1 4
    _ = reader
}

Java¶

import java.util.*;

public class KthInRange {
    static final class Node {
        int cnt; Node left, right;
        Node() {}
        Node(int cnt, Node l, Node r) { this.cnt = cnt; this.left = l; this.right = r; }
    }
    static int D;

    static Node build(int lo, int hi) {
        if (lo == hi) return new Node();
        int mid = (lo + hi) >>> 1;
        return new Node(0, build(lo, mid), build(mid + 1, hi));
    }

    static Node insert(Node p, int lo, int hi, int g) {
        if (lo == hi) return new Node(p.cnt + 1, null, null);
        int mid = (lo + hi) >>> 1;
        if (g <= mid) {
            Node l = insert(p.left, lo, mid, g);
            return new Node(l.cnt + p.right.cnt, l, p.right);
        } else {
            Node r = insert(p.right, mid + 1, hi, g);
            return new Node(p.left.cnt + r.cnt, p.left, r);
        }
    }

    static int kth(Node l, Node r, int lo, int hi, int k) {
        if (lo == hi) return lo;
        int mid = (lo + hi) >>> 1;
        int leftCnt = r.left.cnt - l.left.cnt;
        if (k <= leftCnt) return kth(l.left, r.left, lo, mid, k);
        return kth(l.right, r.right, mid + 1, hi, k - leftCnt);
    }

    static int lowerBound(int[] arr, int v) {
        int lo = 0, hi = arr.length;
        while (lo < hi) { int m = (lo + hi) >>> 1; if (arr[m] < v) lo = m + 1; else hi = m; }
        return lo;
    }

    public static void main(String[] args) {
        int[] a = {3, 1, 4, 1, 5};
        int n = a.length;

        int[] sorted = a.clone();
        Arrays.sort(sorted);
        int[] uniq = Arrays.stream(sorted).distinct().toArray();
        D = uniq.length;

        Node[] roots = new Node[n + 1];
        roots[0] = build(0, D - 1);
        for (int i = 1; i <= n; i++) {
            roots[i] = insert(roots[i - 1], 0, D - 1, lowerBound(uniq, a[i - 1]));
        }

        int[][] queries = {{2, 4, 2}, {1, 5, 3}, {1, 5, 1}, {3, 5, 2}};
        StringBuilder sb = new StringBuilder();
        for (int[] q : queries) {
            int g = kth(roots[q[0] - 1], roots[q[1]], 0, D - 1, q[2]);
            sb.append(uniq[g]).append('\n');
        }
        System.out.print(sb); // 1 3 1 4
    }
}

Python¶

import sys, bisect
input = sys.stdin.readline
sys.setrecursionlimit(1 << 20)


class Node:
    __slots__ = ("cnt", "left", "right")

    def __init__(self, cnt=0, left=None, right=None):
        self.cnt, self.left, self.right = cnt, left, right


def build(lo, hi):
    if lo == hi:
        return Node()
    mid = (lo + hi) // 2
    return Node(0, build(lo, mid), build(mid + 1, hi))


def insert(p, lo, hi, g):
    if lo == hi:
        return Node(p.cnt + 1)
    mid = (lo + hi) // 2
    if g <= mid:
        l = insert(p.left, lo, mid, g)
        return Node(l.cnt + p.right.cnt, l, p.right)
    r = insert(p.right, mid + 1, hi, g)
    return Node(p.left.cnt + r.cnt, p.left, r)


def kth(l, r, lo, hi, k):
    if lo == hi:
        return lo
    mid = (lo + hi) // 2
    left_cnt = r.left.cnt - l.left.cnt
    if k <= left_cnt:
        return kth(l.left, r.left, lo, mid, k)
    return kth(l.right, r.right, mid + 1, hi, k - left_cnt)


def solve(a, queries):
    n = len(a)
    uniq = sorted(set(a))
    D = len(uniq)
    roots = [build(0, D - 1)]
    for v in a:
        roots.append(insert(roots[-1], 0, D - 1, bisect.bisect_left(uniq, v)))
    out = []
    for (l, r, k) in queries:
        g = kth(roots[l - 1], roots[r], 0, D - 1, k)
        out.append(uniq[g])
    return out


if __name__ == "__main__":
    a = [3, 1, 4, 1, 5]
    qs = [(2, 4, 2), (1, 5, 3), (1, 5, 1), (3, 5, 2)]
    print(*solve(a, qs))  # 1 3 1 4

Follow-up extensions an interviewer may ask¶

1. Number of elements ≤ x in a[l..r]. Descend by value; sum left counts (version[r]−version[l−1]) where the node's value range ⊆ (-∞, x]. O(log n).
2. Count of values in [x, y] for a[l..r]. A range query on the difference of the two versions. O(log n).
3. Forced-online queries (each (l,r,k) XORed with the previous answer). Persistent segtree handles it directly; Mo's cannot.
4. Memory under pressure. Move to an arena (int32 children) + lazy-empty version 0 → O(m log n) memory; or switch to a wavelet tree for half the memory.
5. K-th with updates. Combine with a BIT of persistent trees, or use a merge-sort-tree-on-BIT — discuss the O(log²n) cost.

Mock Interview Walkthrough — "Range K-th, 45 Minutes"¶

A realistic end-to-end flow showing how to drive the problem from clarification to optimized code.

Minute 0–3 — Clarify. - "Is the array static or do values change?" → static (if dynamic, flag the O(log²n) variant). - "Are queries online (one at a time, possibly dependent) or can I batch them?" → if forced-online, persistent/wavelet; if offline, mention Mo's as an alternative. - "Value range?" → if huge, I'll coordinate-compress. - "Constraints on n, q?" → sets the target: n, q ≤ 2·10^5 ⇒ need O((n+q)log n), so O(log n)/query.

Minute 3–8 — State the approach out loud. "I'll build a persistent segment tree over the compressed value axis. Version i is the histogram of the first i elements. For a query (l,r,k) I subtract version[l−1] from version[r] node-by-node while descending, using the left-half count to choose a direction. Build O(n log n), query O(log n), memory O(n log n)."

Minute 8–12 — Draw the small example. Use a=[3,1,4,1,5], show the prefix histograms table, walk the (2,4,2)→1 descent. This proves you understand it before coding.

Minute 12–30 — Code it. Write build, insert (path copy), kth (two-version descent), and the compression + driver. Use the language you're strongest in; the Go/Java/Python solutions in this file are the reference.

Minute 30–38 — Test. Run the sample, then call out edge cases: k=1 (min), k=r−l+1 (max), l=r (single element), duplicate values, value below/above all.

Minute 38–45 — Optimize / discuss. Mention the arena for memory/GC, lazy-empty version 0, lock-free reads, and the wavelet-tree alternative if memory is tight. If asked for follow-ups, do "count ≤ x in range" (one more descent variant).

What separates a hire from a no-hire here¶

Implementation Pitfalls Deep-Dive¶

Interviewers love to probe whether you've actually written this. Be ready for these.

1. "Your old version's query changed after an update — what happened?" You mutated a shared node. The classic slip is writing node.cnt += 1 on the recursion's input node instead of allocating a fresh one. Fix: every recursion level constructs a new node; never assign into a field of the argument.

2. "Your k-th returns the wrong value off-by-one." Two usual causes: (a) using version[l] instead of version[l−1]; (b) k indexing — the algorithm is 1-based (k=1 is the minimum), so if k <= leftCount (not <). Walk the boundary k=leftCount to confirm.

3. "Out of memory at n=10^6." You used heap objects (24 B + header) or forgot lazy-empty. Switch to an arena (int32 children, ~12 B) and make version 0 a sentinel so total is O(m log n), not O(n + m log n).

4. "Stack overflow on the judge." Deep recursion. In Python sys.setrecursionlimit(1<<20); in any language consider an iterative descent for kth (a simple while-loop, since it never branches).

5. "It's correct but TLE." Function-call overhead and pointer chasing. Inline the descent, use the arena (contiguous memory → fewer cache misses), and avoid recomputing rank inside the hot loop (precompute compressed values once).

6. "How do you test it without a judge?" Brute force: for random arrays and random (l,r,k), sort a[l..r] and compare the k-th. Also a persistence test: snapshot results, run more updates, re-query old versions, assert unchanged.

Additional Tiered Questions (Bank B)¶

Sample full answer — B10 (group vs monoid): "The k-th subtraction relies on version[r] − version[l−1] giving the sub-range's per-bucket value. Subtraction requires an inverse — counts live in the group (ℤ, +, 0), so it works. Min and max form a monoid (associative with identity ±∞) but have no inverse: knowing min(a[1..r]) and min(a[1..l−1]) doesn't recover min(a[l..r]). So persistence still lets you do a range-min query on any single version, but the prefix-difference k-th trick is specific to additive (group) aggregates."

Quick Self-Test (cover the answers)¶

1. How many nodes does one update allocate, for n = 16? → 5 (log₂16 + 1).
2. Total memory for m = 10^5 versions, n = 10^5? → O(n log n) ≈ 1.9·10^6 nodes.
3. Which version do you subtract for a[l..r]? → version[l−1].
4. Is the k-th query online-capable? → Yes.
5. Partial or full persistence for k-th? → Partial (linear version chain).
6. One-sentence reason reads are lock-free? → Nodes are immutable, so readers never race a writer.
7. Cheapest way to cut memory in half vs. persistent tree? → Use a wavelet tree (loses versioning).
8. What real system is this pattern? → MVCC / COW filesystems / Git / functional vectors.

Closing Checklist¶

• Can explain path copying and the ⌈log₂ n⌉+1 allocation count.
• Can derive O(n + m log n) space and contrast with naive O(nm).
• Can build prefix versions and answer range k-th in O(log n), live, in one language.
• Can state partial vs full persistence and which the k-th needs.
• Can compare against merge-sort tree, wavelet tree, and Mo's, and justify the choice.
• Can discuss arenas, lock-free reads, and MVCC analogy for a systems round.

One-Liners to Memorize¶

• Persistence = keep every version queryable after updates.
• Path copying = clone only the ⌈log₂ n⌉+1 nodes on the update path; share the rest.
• Nodes are immutable — that's what keeps old versions correct and reads lock-free.
• k-th in a[l..r] = walk version[r] and version[l−1] down the value axis using leftCount = right.left.cnt − left.left.cnt.
• Subtract version[l−1], not version[l].
• Memory = O(n + m log n); lazy-empty makes it O(m log n); naive copy is O(nm).
• Partial persistence (read any, write latest) is all k-th needs.
• Online: persistent/wavelet yes, Mo's no.
• Same pattern as MVCC, ZFS/Btrfs snapshots, Git, functional vectors.
• Memory-tight read-only? Prefer a wavelet tree.

Next step: Drill the graded exercises in tasks.md — build, query, k-th, count-≤-x, and a persistence-immutability stress test, all in Go, Java, and Python.