Project: audit ranks, bursts, tariffs, count extremes, and routes

Last updated: 5 Oct 202640 min read

project

A dispatch console has five different lookup contracts. A historical shipment interval needs its kth priority; a fault-score interval needs its best contiguous burst after corrections; a tariff applies only during certain minutes; an alert counter needs keys at both frequency extremes; and an address needs its longest valid route prefix. Implement these as separate indexes, because each stores different invariants and accepts different mutations. The first array is frozen, the burst tree permits point replacement, the tariff index adds interval-limited lines, the counter increments or decrements keys by one, and the compressed route trie inserts or replaces destinations.

Acceptance trace

For priorities [47,19,61,29,19,83,37], rank three in [1,6) is 29. For fault scores [-8,47,-19,61,-83,29,37], the best nonempty burst is 89; replacing -83 with -17 makes it 138. For the three tariff offers in the working program, minute ten costs 39 and minute fifteen costs 44. For the alert stream, dock-61 starts as the unique minimum-count key and dock-47 as the unique maximum. For the routing table, addresses 178, 190, 171, and 132 choose north, south, regional, and default destinations. Keep these values as independent acceptance checks, not as data copied between structures.

Failure and cost review

Enumerate sorted subarrays, nonempty contiguous sums, active tariff lines, direct key counts, and matching route prefixes for small inputs. Reject an empty kth interval and an invalid rank; keep duplicate priorities. Test an all-negative burst and a correction at either endpoint. Query a minute with no active tariff to confirm the no-result path, and confirm an offer's right endpoint is excluded. Mix count increments with decrements through bucket removal, allowing any tied extreme key. Insert a short route after longer descendants so the compressed edge must split without losing them. Report each structure's separate construction, query, update, and storage cost.

Common Mistakes

Do not count values outside the requested prefix-root difference.
Do not let an empty burst win a nonempty query.
Do not evaluate a tariff outside its valid minutes.
Do not assign stable order to tied frequency keys.
Do not stop route matching after checking only one bit of a compressed edge.

Connected lessons

data structures

projects