Skip to main content

Capstone: An Exact Index With Historical Range Queries

Build a single-threaded CLI index over a fixed ordered catalogue of integer keys. Each version maps some catalogue keys to integer quantities; an absent key contributes zero to range sums but differs from a present key with quantity zero in exact lookup. Use a catalogue-to-position mapping, an authoritative presence/value record and a range-sum structure. Define duplicate replacement, invalid keys, empty ranges and version IDs explicitly.

Estimated effort: 8–12 hours after the core. This is a synthetic teaching service; concurrency, crash durability and transactions are separate requirements.

Stage 1: exact current state​

Support set, delete, exact lookup and range sum by catalogue positions [l,r). Use your AVL map for authoritative current membership and Fenwick or a justified sum tree for quantities. Replacement uses the difference between new and old quantity for a point-add structure. Deleting an absent key follows a documented policy. Confirm the exact map and range totals remain synchronized after every operation.

Fixture catalogue [10,20,30,40], initially only {10:1,30:3}: total is 4. Set 20 to 2, replace 30 with -1, and delete 10. Current contents are {20:2,30:-1}, total 1. Key 40 is absent; explicitly setting it to zero changes membership but not the sum.

Stage 2: preserve and branch history​

Add snapshot/version IDs and set/delete from any retained version. PersistentSum can provide point-set sum roots, but it does not store presence. Keep an authoritative presence/value snapshot per version, or derive a persistent ordered-map extension. The straightforward baseline may copy a dictionary per version; state its O(number of present keys) copying cost rather than claiming the entire service now updates in O(log n).

From the stage-1 snapshot {20:2,30:-1}, fork one version setting 10 to 5 (sum 6), and another deleting 30 (sum 2). The original still sums to 1. Expose exact lookup and range sum for every retained version, including branches from an older version after newer versions exist. Presence cannot be inferred from nonzero quantity because stored zero is legal.

Stage 3: add a Bloom negative shortcut​

Maintain an insertion-only filter containing every key ever made present in any published retained version. A negative can skip the exact lookup; a positive must check the requested version's authoritative record. Do not treat positives as membership or clear shared bits on deletion. For this single-threaded model, set filter bits before publishing a version containing a new key. If publication fails, extra positive bits are safe for exactness; missing bits are not.

A rebuild may use the union of keys present across all versions that will use the rebuilt filter. Building from only the latest version can create false negatives on an old branch. Keep the old filter active until the complete new one is ready, or disable negative shortcuts during rebuild. This is lifecycle reasoning, not a claim of lock-free publication.

Independent verification​

Keep copied dictionaries and plain arrays as a tiny oracle. Generate set/delete, lookup, range-query and branch operations; compare exact membership, quantities and every version's ranges. Include present-zero versus absent, negative quantities, replacements, catalogue boundaries, old branches, empty ranges and invalid operations.

Force collisions with m=k=1. Service answers must remain identical to exact-only answers despite many extra lookups. Construct a filter missing an old-version key and demonstrate why the negative shortcut fails; then test the repaired rebuild. Measure exact lookups avoided, false positives/denominator and end-to-end work separately from the ideal probability estimate.

Deliverables and acceptance​

  • Runnable CLI with fixtures for all three stages and documented exceptions.
  • Representation and synchronization invariants, plus immutable version semantics.
  • Stateful model comparisons and explicit stale-filter/aliasing counterexamples.
  • Resource memo including catalogue storage, exact snapshot copying, retained roots/nodes, filter bytes/hash work and output costs.
  • One measured operation mix with environment and included work; one fresh changed requirement after 7–14 days.

Accept exact outputs for every retained version. Reject a service that uses Bloom positives as truth, misses old keys on a negative shortcut, conflates zero with absent, corrupts prior versions or hides snapshot copying in its bound. Score C1/C5/C6/C7/C8 and record actual assistance and repairs.