Assessment Solutions and Scoring

Read after preserving an attempt. Equivalent valid shapes and representatives are acceptable when invariants and API outputs agree. Apply competency levels, not a scalar percentage that can hide critical failures.

A1 / C1: ordered map

Insert 4,2,3 gives a left-right repair: rotate left at 2, then right at 4. Root 3 has leaves 2,4. Replace 2's payload with 99; delete 4. Items are [(2,99),(3,30)], rank(3)=1, select(0)=(2,99). Root height 2 and size 2; remaining leaf height/size 1. Inspect inherited bounds, acyclicity, unique node identity and independently recomputed metadata. Compare rank/select with sorted dictionary entries, not the tree's own traversal alone.

Level 2: correct mutation trace, metadata dependency order, O(log n) path operations and O(n) traversal, plus red-black proof outline from equal black paths/no adjacent reds. Knowing a balancing name without its invariant is insufficient.

A2 / C2: partition

Flags: true,true,true,true,false. Final sets {0,1,2,3}, {4,5}, {6}; count 3 and sizes 4,2,1. Each size-based depth increase at least doubles the containing component, giving logarithmic depth without compression. The standard combined-heuristic theorem yields O(n+q*alpha(n)) aggregate work after initialization under a specified convention/model; the doubling argument alone is not that proof. Deleting 1-2 alone does not split this graph: the previously redundant edge 0-3 still connects the two pairs, via path 1-0-3-2. Deleting 0-3 afterward does split it into {0,1} and {2,3}; with {4,5} and {6}, the graph now has four components. Ordinary DSU still retains the old three-component partition. A union that leaves the partition unchanged can nevertheless add a graph edge essential after a later deletion. Parent links may be representation shortcuts rather than input edges.

Level 2: idempotent unions, arbitrary valid roots, initialization cost and deletion/path-witness limits. Use an independent graph/component model for checks.

A3 / C3: heap

Seven elements occupy degrees 0,1,2; adding a singleton carries through all three, leaving degree 3 with eight nodes. Destructive meld empties the donor; equal priorities remain separate occurrences, empty pop raises IndexError and self-meld ValueError before change. Push into the emptied donor and verify the receiver's drain does not include that new key; inspect node identities across all live heaps as a stronger check.

Level 2: correct degrees, counts, order/ownership, implementation-specific carry costs and separation of local pairing-heap work from its sequence analysis. Fibonacci decrease-key guarantees cannot be copied onto an unspecified pairing variant.

A4 / C4: ledger

First five actual append costs are [1,2,3,1,5]; capacities after each are [1,2,4,4,8], potentials [1,2,2,4,2] from initial zero. Amortized charges are [2,3,3,3,3]; actual total 12 equals charged 14 minus final potential 2. General copied capacities sum to less than 2n; writes add n. First allocation is handled separately. For the queue, Phi=2*len(In); a transfer dequeue costs 2k+1 and drops potential 2k, charge 1. Enqueue charge is 3.

Level 2: consistent primitive units, every operation case, nonnegative reachable potential and telescoping with initial budget. These are sequence guarantees; they do not prevent long individual pauses or account for all runtime allocation costs.

A5 / C5: update algebra

After assignment: [2,4,4,4]; after addition: [0,2,2,4]. Total 8, sum [1,3)=4. Action on sum S and length L is a*S+b*L. New-after-old composition is (a2*a1,a2*b1+b2). Assignment-zero (0,0) differs from identity (1,0). Push before partial descent and pull after partial mutation. Core Fenwick supports point add and prefix/range sum, not direct arbitrary range assignment; simulating it by per-element work changes complexity.

Level 2: derived action/composition and mixed sequence checks with empty ranges, negative values and deferred tags. Do not claim generic lazy support from associativity alone.

A6 / C6: history

Version sums are 20 for [2,4,6,8], 26 for [2,10,6,8], and 12 for [2,4,-2,8]. The first branch shares the original right half, the second the original left half. Modified paths are new immutable nodes. Initial build O(n); each branch/query O(log(n+1)); q retained updates use O(n+q*log(n+1)+q) node/root storage. Starting the second update from the latest root would yield [2,10,-2,8] with sum 18, a different answer.

Level 2: every old version checked after each fork, explicit structural sharing, retention accounting, and distinction from database durability/transaction guarantees.

A7 / C7: filter

Approximate m≈9585.1; choose m=9586,k=7, byte payload 1199. Independence, uniform placement, distinct count and sample/query assumptions constrain the sizing estimate; SHA-256-derived positions are not a proof of independent hashes. One-bit filter says possibly present for B; exact store must return absent.

In a single-threaded service, set filter bits before making a newly inserted exact key visible, or otherwise disable negative shortcuts until synchronized. An extra positive after a failed insertion is safe for exactness because it still triggers confirmation; a visible exact key missing its bits is unsafe. Deletion may leave stale positives. Rebuilding must cover all keys in all versions for which that rebuilt filter will be used.

Level 2: conditional no-false-negative proof, positive confirmation, byte/parameter cost and separate observed false-positive counts/denominators. A measured zero rate does not establish a universal probability zero.

A8 / C8: model and transfer

Union bound gives 1024/2^20=1/1024 for any tower height at least 20. This height event is not itself a full search-time tail proof. Expected costs average over specified internal randomness; amortized costs bound sequences; worst-call costs constrain each operation. None is interchangeable with one workload's observed mean.

For old-version range queries, use explicit version IDs with persistent sum roots and immutable sharing, or another justified historical representation. Test branches from old roots and all retained versions against snapshot arrays. Tree shape excludes arbitrary keys/values; ideal-cache transfers require the stated model and do not directly predict allocation/locality behavior on actual hardware.

Level 2: coherent revised API, proof and resource account, independent stateful checks and explicit model limits. Level 3 requires an unseen changed requirement solved independently, not repeating this key's example.