Skip to main content

Advanced Structures: Case Studies

These are synthetic scenarios, not verified company incidents. Deliver a contract, small separating sequence, design decision and verification evidence for each.

Case 1: the ranking map with stale sizes​

Lookup tests pass after AVL rotations, but rank/select return incorrect positions. Explain why sorted traversal alone is insufficient. Inspect exact size metadata and compare all ranks after mixed deletion/replacement against a separate sorted dictionary. Record the first operation that violates the metadata invariant.

Case 2: the queue merger with shared ownership​

Two schedulers meld their heaps, then continue using both objects. A job appears twice or a later mutation changes the other queue. Define destructive versus copying meld and handle/identity expectations. Use all-live-heap node-ownership checks and donor-reuse traces. Do not claim logical copying is free.

Case 3: the low-latency append service​

An append benchmark has a good average, but requests near resize boundaries experience long pauses. Use the copy/write ledger to explain what amortized constant means. Compare reserving capacity or a separately specified incremental rebuild design. Record actual cost distribution and included allocation/GC work; neither geometric analysis nor one mean timing proves a latency budget.

Case 4: the range updater that loses assignments​

Range assignment and addition work separately but fail when mixed. Derive the sum action and chronological tag composition. Use assign-zero, assign-then-add, and overlapping subranges to distinguish broken variants. The correct aggregate identity is not the same as an absent update tag.

Case 5: the historical lookup shortcut​

A Bloom filter rebuilt from the current version omits a key still present in an old version. A negative shortcut now returns a wrong old-version result. Use the capstone to define the population covered by a filter, safe single-threaded publication and exact positive confirmation. Test forced collisions and stale filters separately; they fail in different directions.