Project: audit slot, distinct, text, median, and ball indexes

Last updated: 5 Oct 202640 min read

project

Build five separate indexes for a dispatch console. Loading bays disappear permanently as they are claimed. Incident codes repeat in a frozen log, and reports ask for the count of distinct codes in selected intervals. A fixed-length alert string receives character replacements and needs fast candidate-equality checks. Dispatch waits slide through a fixed-width median window. Static depot coordinates need exact nearest lookup. The indexes have different ownership rules: successor links only move forward, prefix roots are immutable, text hashes can collide, expiring heap records may remain stale, and metric balls only prune when their distance bounds permit it.

Acceptance trace

Reserve bays two, three, and six in a nine-bay index, then claim from two twice to receive four and five. Count three distinct codes in the first five entries of [A-47,B-19,A-47,C-61,B-19,D-83]. In dock47dock47, the two six-character spans match until the final 7 is replaced by 9. For waits [47,19,61,29,83,37,19], width-three lower medians are [47,29,61,37,37]. For the six-depot coordinate set, (5,2) selects D-47. Validate each answer against a direct small-input model before relying on an index.

Failure and cost review

Exhaust a slot universe and confirm that its sentinel is never returned as a real bay. Query an empty distinct interval and an earlier prefix version after later duplicates appear. Replace and restore a text character, but do not call equal fingerprints a proof of exact identity. Force repeated wait values and expired entries buried in a heap; compare each window median with a sorted slice. Use overlapping depot balls and tied distances to exercise the exact leaf scan and deterministic tie rule. Record the worst-case cost as well as the common-case reason for each structure.

Common Mistakes

Do not reopen a slot in a forward-only successor index.
Do not count an incident twice in a single range.
Do not treat a finite hash as collision-free.
Do not balance heaps using stale entries.
Do not prune a ball from its center distance alone.

Connected lessons

data structures

projects