Efficient High-Dimensional Vector Search | Dataford Interview Questions

Given a large dataset, how would you implement an efficient search algorithm to query high-dimensional vector embeddings?

Implement locality-sensitive hashing using deterministic random-hyperplane signatures. Build multiple hash tables, gather vectors sharing a bucket with each query, and return the nearest candidates by squared Euclidean distance. If fewer than top_k candidates are found, search the full dataset to guarantee enough results.

The function receives vectors and queries as lists of equal-length numeric lists and returns one list of vector indices per query. Results must be ordered by increasing distance, with smaller indices breaking ties.

Signature: def lsh_vector_search(vectors, queries, num_tables, num_planes, top_k, seed):

Constraints

1 <= len(vectors) <= 5000
1 <= len(queries) <= 500
1 <= len(vectors[i]) <= 256
All vectors and queries have the same dimension
1 <= num_tables <= 20
1 <= num_planes <= 20
1 <= top_k <= len(vectors)
Coordinates are finite integers
Results are ordered by squared Euclidean distance, then by index

Function Signature

def lsh_vector_search(vectors, queries, num_tables, num_planes, top_k, seed):

Your question is Efficient High-Dimensional Vector Search. Start with the requirements in the Question tab.

Run and submit as often as you like. When you're ready, talk me through your approach or go straight to the code.

Problem