Skip to main content

Case Studies

These are synthetic engineering cases, not claims about measured incidents.

Equal-key audit records​

A report groups records by status but must preserve arrival order within status. A replacement sorter compares whole records and silently orders payload strings. Write the key contract, preserve a two-record regression, and choose stable key-only sorting or an explicit arrival sequence. Explain how an arrival sequence differs from arbitrary payload order. Evidence: tagged outputs and merge invariant.

Deletion-heavy cache​

A linear-probing cache has few live entries but many tombstones after churn. Lookup paths remain long. Deleting to empty would corrupt reachability; increasing capacity is not always the right response. Track live and used occupancy, rebuild when appropriate, and test update-after-delete histories. Evidence: operation trace, probe counts with stated exclusions, and model comparison.

One percentile versus many rank queries​

A batch needs one exact rank, then requirements expand to hundreds of rank queries on the same data. Compare selection, sorting once, and a persistent index. Include input copies and preprocessing. If approximate streaming quantiles are proposed, record that accuracy and output contracts have changed. Evidence: cost expressions and a workload-specific experiment, not an unconditional winner.

Merge under a memory budget​

Sorted shard iterators exceed RAM in aggregate. Keep one head per stream and stream output. Global FIFO ties cannot be inferred from shard-local order alone; the producer must supply sufficient metadata and sortedness. Evidence: guarded generators, tie fixtures and O(K) state argument. File buffering and crash recovery are additional requirements, not solved by the in-memory lab.

Scheduler cancellation​

Cancelled jobs remain as stale heap entries, so live job count understates memory. Choose indexed deletion or lazy versioning with cleanup. Test cancellation followed by identity reuse and equal priorities. Evidence: identity/version invariant, physical entry counts and a policy for bounded retained state.