Geometry, sweep, simulation, and parsing · HTML
Given operations and bounds, list each operation's reads and writes, choose complementary structures, and define synchronized updates for every duplicate representation.
Recognition signals
- A class or online API must be implemented
- Operations require different access directions
- Target complexities are explicit
- One container cannot satisfy every operation
- Caches, sets, iteration, or ranking are maintained
False friends
| Signal | Why it is different |
|---|
| One offline computation | If every operation is known in advance, sorting or batching may be simpler than an online structure. |
| Excess duplicated state | Every derived copy adds a synchronization obligation and a path to ghost entries. |
Core invariant
Every logical element has consistent representations across indices; primary storage owns truth and auxiliary indices only accelerate access.
State, transition, and processing order
| Item | Definition |
|---|
| State | Choose arrays, hashes, heaps, or linked lists from operation needs; the example IndexedSet pairs items with reverse positions. |
| Transition | Each public operation checks preconditions and updates every structure in an order that preserves needed references, restoring the invariant before return. |
| Frontier / order | There is no traversal frontier; each API-call boundary is a transaction boundary at which the full invariant must hold. |
Python skeleton
class IndexedSet:
def __init__(self):
self.items = []
self.pos = {}
def add(self, value):
if value in self.pos: return False
self.pos[value] = len(self.items)
self.items.append(value)
return True
def remove(self, value):
if value not in self.pos: return False
i = self.pos.pop(value)
last = self.items.pop()
if i < len(self.items):
self.items[i] = last
self.pos[last] = i
return True
def contains(self, value):
return value in self.pos
def at(self, index):
return self.items[index]
Correctness sketch
- Initially both array and map are empty, so the bidirectional correspondence holds.
- add appends a new value and records exactly that position.
- remove fills the hole with the last value and updates the moved value's position.
- All other positions remain unchanged, restoring the invariant before each return.
Complexity
| Time | Space | Parameters |
|---|
| Amortized O(1) add/remove/contains and O(1) at | O(n) | n current elements; bounds rely on amortized hashing |
Edge cases
- Duplicate add
- Removing a missing value
- Removing the last array element
- at on an empty or invalid index
- Mutable objects are unsuitable stable hash keys
Error patterns
| Pattern | Why it fails / fix |
|---|
| Not updating the moved index | The last value keeps a stale position after hole filling. |
| Popping before preserving needed data | Mutation order must retain every value needed later. |
| Testing outputs but not invariants | After random operations, verify both directions between pos and items. |
Selection and exclusion rules
- Write an API-versus-complexity table before choosing structures.
- For every redundant representation, state its synchronization duty.
- For unordered O(1) array deletion, fill the hole with the last item.
- If order must be stable, use a linked structure or tree instead.
Original micro-example
| Part | Detail |
|---|
| Result | items may become [a,c], with positions a→0 and c→1. |
| Scenario | Add a, b, c to an IndexedSet, then remove b. |
| Walkthrough | Move final item c into b's hole and change c's reverse index from 2 to 1. |
Recall prompts
My notes