Implement a VectorIndex that stores embedding vectors and finds nearest neighbors by cosine similarity, using nothing but numpy. Where the other Tier 4 problems build a training pipeline end to end, this one builds one serving path of a real vector search engine: brute force → approximate (LSH) → incremental deletion → filtered search. Randomness is used only to generate the LSH hyperplanes — everything else is deterministic.

Shared spec

Vectors arrive as lists of floats whose length is always dim (you may use numpy internally, but the public API always accepts and returns plain Python lists). id is a string.

index = VectorIndex(dim=4, n_hyperplanes=0, seed=0)
index.add(id, vector)
index.search(query, k)

Cosine similarity

$\text{sim}(a, b) = \frac{a \cdot b}{\lVert a \rVert \lVert b \rVert}$

If either norm is zero, the similarity is exactly 0.0 — not an exception, not nan. This is not an edge case left undefined; it is a boundary rule you must honor.

Sort tie-breaking — the shared convention

Every search in this problem sorts by similarity descending, breaking ties by id ascending (the same score-ordering convention as the other Tier 4 problems).

add is an upsert

Calling add again with the same id overwrites that vector — it does not stack a second entry. When n_hyperplanes > 0, the signature is recomputed from the new vector immediately (no lazy evaluation).

LSH hyperplane protocol — follow this exactly

With n_hyperplanes = 0 (the default) LSH is off — approximate search must behave exactly like brute force (a regression safeguard).

With n_hyperplanes > 0, the constructor (and rebuild()) creates rng = np.random.default_rng(seed) exactly once and draws the hyperplanes in this order, count, and shape:

hyperplanes = [rng.normal(0, 1, size=dim) for _ in range(n_hyperplanes)]

For each stored vector, compute its signature (a tuple of n_hyperplanes bits) once, at add time — never again afterwards. Bit i is 1 when dot(vector, hyperplane_i) >= 0, otherwise 0. Queries are not stored, so their signature is computed on the spot the same way on every search.

LSH candidate pool — Hamming distance ≤ 1

The candidate pool for approximate search is every stored vector whose signature is within Hamming distance 1 of the query's (i.e. at least n_hyperplanes - 1 of the n_hyperplanes bits match). This is always a fixed distance of 1, not a threshold that scales with n_hyperplanes — a deliberate approximation rule so buckets do not come up empty on small test data.

When the candidate pool is empty, fall back to brute force over every stored vector (approximate search must never return fewer results than brute force could fill).

rebuild() regenerates with the same seed

When n_hyperplanes > 0, rebuild() regenerates the hyperplanes from scratch with the same seed (following exactly the constructor's protocol, so the result is bit-for-bit identical to a freshly built index) and recomputes every stored vector's signature against the new hyperplanes. With n_hyperplanes == 0, rebuild() does nothing.

Level structure

Each level must preserve the behavior of the previous ones. With n_hyperplanes=0, search_approx and search_filtered always operate on the same candidate pool as search (brute force).

At this level n_hyperplanes and seed are only accepted (to fix the constructor signature) and never actually used. Implement brute-force cosine similarity search only.

VectorIndex(dim: int, n_hyperplanes: int = 0, seed: int = 0)
add(id: str, vector: list[float]) -> None
search(query: list[float], k: int) -> list[str]

• Cosine similarity: dot(a,b) / (norm(a) * norm(b)). If either norm is zero the similarity is 0.0 (not an exception, not nan).
• add: when the id already exists, overwrite the vector (upsert) — do not stack a second entry.
• search: sort ids by similarity descending, ties by id ascending, and return min(k, stored count) of them. Return [] when k <= 0 or nothing is stored.
• Whether the query vector itself lives in the index is irrelevant — a query is just input, not a stored id.
• Mismatched dim is out of spec (assume it always matches).