Data structures and algorithms for ML quiz

Question 1

Why does the average query time of a KD-tree for exact nearest-neighbor search degrade toward O(n) as dimensionality grows?

Accepted Answer

Distance contrast collapses so the pruning bound rarely excludes subtrees, forcing visits to nearly all leaves

Answer

The tree becomes unbalanced and rotations dominate runtime

Answer

Floating-point error makes comparisons unreliable in high dimensions

Answer

Memory cache misses scale linearly with dimension

Question 2

What advantage do ball trees have over KD-trees for nearest-neighbor search, and when does it matter?

Accepted Answer

They use hyperspheres and the triangle inequality, pruning better for non-axis-aligned and arbitrary-metric data

Answer

They support only Euclidean distance with O(1) queries

Answer

They guarantee O(log n) queries in any dimension

Answer

They require no tree construction step

Question 3

In HNSW (Hierarchical Navigable Small World) graphs, what is the role of the multiple layers and what query complexity do they enable?

Accepted Answer

Upper sparse layers provide long-range links so greedy search reaches the target neighborhood in ~O(log n) hops

Answer

Layers store exact distances to enable binary search, giving O(log n) exact results

Answer

Each layer is an independent k-d tree voted by majority

Answer

Layers replicate the data for fault tolerance, not for speed

Question 4

How does Locality-Sensitive Hashing (LSH) achieve sublinear approximate nearest-neighbor search?

Accepted Answer

Hash collision probability grows with similarity, so only same-bucket candidates are compared

Answer

It sorts points by hash value so binary search finds neighbors

Answer

It compresses vectors so exact distances become cheap

Answer

It builds a balanced BST keyed on hash values

Question 5

What is Product Quantization (PQ) and why is it effective for compressing vectors in billion-scale similarity search?

Accepted Answer

It splits vectors into subspaces, k-means quantizes each to a codebook, and stores compact centroid ids with table-based distance lookup

Answer

It applies PCA then stores top components as float16

Answer

It hashes vectors to integers and compares Hamming distance

Answer

It uses Huffman coding on raw float bytes

Question 6

In an IVF (inverted file) vector index, what does the nprobe parameter control and what tradeoff does it create?

Accepted Answer

The number of nearest Voronoi cells scanned, trading recall against latency

Answer

The number of bits per quantized code, trading memory for accuracy

Answer

The branching factor of an internal tree

Answer

The number of hash tables used

Question 7

What data structure efficiently maintains the top-k largest elements from a large or streaming dataset, and what is its complexity?

Accepted Answer

A min-heap of size k, O(n log k) time and O(k) space

Answer

A max-heap of size n, O(n log n) time

Answer

A balanced BST of size n, O(n) space

Answer

A hash map, O(n) time and O(n) space

Question 8

When would you choose Quickselect over a heap to find the k-th smallest element, and what is its complexity?

Accepted Answer

When the full array is in memory; Quickselect is expected O(n) vs O(n log k) for a heap

Answer

When data streams and cannot be stored; Quickselect is O(log n)

Answer

Always, because Quickselect is worst-case O(n)

Answer

Never, heaps are strictly faster

Question 9

What does a Count-Min Sketch estimate, and what kind of error does it have?

Accepted Answer

Frequency estimates that may overestimate but never underestimate, with bounded error

Answer

Exact item counts in O(1) memory

Answer

Distinct-element cardinality with no error

Answer

Median of a stream with two-sided error

Question 10

What problem does HyperLogLog solve, and roughly what accuracy does it give for its memory?

Accepted Answer

Approximate distinct-element cardinality with ~2% error in kilobytes of memory

Answer

Exact distinct counts in O(n) memory

Answer

Top-k frequent items with no error

Answer

Quantile estimation of a stream

Question 11

What guarantees and failure mode does a Bloom filter provide for membership testing?

Accepted Answer

No false negatives but possible false positives, and no deletions

Answer

No false positives but possible false negatives

Answer

Both errors possible, supports deletion

Answer

Exact membership with O(1) memory

Question 12

How does reservoir sampling draw a uniform sample of size k from a stream of unknown length in one pass?

Accepted Answer

Keep first k, then accept item i with probability k/i replacing a random slot

Answer

Sort the stream and take the first k

Answer

Take every (n/k)-th element

Answer

Keep the k items with largest random keys, requiring two passes

Question 13

Why is the Union-Find (disjoint-set) data structure with path compression and union by rank useful in ML clustering, and what is its amortized complexity?

Accepted Answer

O(alpha(n)) amortized per operation, effectively constant

Answer

O(log n) per operation due to balanced trees

Answer

O(n) per merge

Answer

O(1) only without path compression

Question 14

What problem does a Fenwick tree (Binary Indexed Tree) solve more efficiently than a prefix-sum array, and at what cost?

Accepted Answer

O(log n) point updates and O(log n) prefix-sum queries on dynamic data

Answer

O(1) updates and O(1) queries

Answer

O(n) queries but O(1) updates

Answer

O(sqrt n) for both operations

Question 15

Why are tries (prefix trees) well suited to subword vocabulary lookup and autocomplete in NLP pipelines?

Accepted Answer

Lookup and prefix enumeration are O(L) in key length, enabling fast longest-prefix matching

Answer

They give O(1) lookup regardless of key length

Answer

They use less memory than hash maps always

Answer

They require sorted input to build

Question 16

What is the time complexity of Dynamic Time Warping (DTW) between two sequences of lengths n and m, and how is it reduced in practice?

Accepted Answer

O(nm) via a DP matrix, reduced by warping-band constraints and lower bounds

Answer

O(n+m) using two pointers

Answer

O(n log n) via FFT

Answer

O(n^2 m^2) and irreducible

Question 17

What does the Viterbi algorithm compute, and what is its complexity for a hidden Markov model with N states over T steps?

Accepted Answer

The most probable hidden state sequence, in O(T*N^2)

Answer

The marginal likelihood, in O(N^T)

Answer

The expected state counts, in O(T*N)

Answer

The stationary distribution, in O(N^3)

Question 18

In sequence decoding, what is the time and memory complexity of beam search with beam width B over vocabulary V for T steps?

Accepted Answer

O(T*B*V) time and O(B*T) memory

Answer

O(T*V) time independent of B

Answer

O(B^T) time (exponential)

Answer

O(T*B) time independent of V

Question 19

Why is topological sorting central to reverse-mode automatic differentiation in deep-learning frameworks?

Accepted Answer

It orders DAG nodes so backprop visits each node after all its consumers' gradients are ready

Answer

It detects NaNs by sorting node values

Answer

It balances the graph for parallelism only

Answer

It is unrelated; autodiff uses BFS

Question 20

What is the feature hashing (hashing trick) technique and what is its main tradeoff?

Accepted Answer

It hashes features to fixed indices for O(1) bounded-memory encoding, at the cost of collisions

Answer

It learns an embedding table requiring full vocabulary

Answer

It guarantees no collisions via perfect hashing

Answer

It compresses dense vectors with PCA

Question 21

How does the Compressed Sparse Row (CSR) format store a sparse matrix, and why is it efficient for sparse matrix-vector multiply?

Accepted Answer

It stores values, column indices, and row pointers, giving O(nnz) SpMV with row locality

Answer

It stores a dense 2D array with zeros included

Answer

It stores only the diagonal

Answer

It uses a hash map per cell, ideal for SpMV

Question 22

What is the time and memory complexity of standard self-attention in a Transformer with sequence length n, and what does FlashAttention change?

Accepted Answer

O(n^2) time and memory; FlashAttention keeps O(n^2) compute but reduces memory to O(n) via tiling

Answer

O(n) time and memory; FlashAttention makes it O(log n)

Answer

O(n^3) time; FlashAttention makes it O(n^2)

Answer

O(n^2) time but O(1) memory already

Question 23

How does MinHash estimate Jaccard similarity between two sets efficiently?

Accepted Answer

The probability two sets share the same min-hash equals their Jaccard, so matching signatures estimate it

Answer

It counts intersecting elements directly in O(1)

Answer

It hashes set sizes and compares them

Answer

It uses cosine of TF-IDF vectors

Question 24

What similarity does SimHash approximate, and what makes it well suited to near-duplicate detection?

Accepted Answer

Cosine/angular similarity, via small Hamming distance between fingerprints

Answer

Euclidean distance, via prefix matching

Answer

Jaccard similarity of multisets

Answer

Edit distance between raw strings

Question 25

What is a skip list, and why might it be preferred over a balanced BST in concurrent ML serving systems?

Accepted Answer

It is a probabilistic structure with expected O(log n) ops that is easier to make concurrent than balanced trees

Answer

It guarantees worst-case O(1) operations

Answer

It only supports insertion, not search

Answer

It requires global rebalancing on every insert

Question 26

How does the power-iteration method compute PageRank, and what determines its convergence rate?

Accepted Answer

By repeated sparse matrix-vector products converging at a rate set by the eigenvalue gap (damping factor)

Answer

By Gaussian elimination in O(n^3), exactly once

Answer

By BFS from the highest-degree node

Answer

By sorting nodes by in-degree

Question 27

Why do large-scale GNNs like GraphSAGE use neighbor sampling instead of full-graph message passing?

Accepted Answer

To bound the exponential neighbor explosion (O(d^L)) so per-node cost and memory stay constant

Answer

To add noise for privacy

Answer

Because graphs must be acyclic

Answer

To avoid floating-point overflow

Question 28

What does the Space-Saving algorithm solve, and how does it bound memory while finding heavy hitters?

Accepted Answer

It keeps O(1/epsilon) counters, evicting the minimum, to report all items above frequency epsilon*N

Answer

It sorts the stream to find the mode in O(n log n)

Answer

It stores exact counts for all items

Answer

It samples the stream uniformly and counts the sample

Question 29

What advantage does cuckoo hashing offer for hash tables used in high-throughput lookup, and what is its main risk?

Accepted Answer

Worst-case O(1) lookups, but insertions can cascade evictions and force rehashing

Answer

Amortized O(1) lookups with no insertion risk

Answer

O(log n) lookups with guaranteed inserts

Answer

It eliminates the need for hash functions

Question 30

Why does Dijkstra's shortest-path algorithm use a priority queue, and what complexity does a binary heap give?

Accepted Answer

To extract the minimum-distance node efficiently; a binary heap gives O((V+E) log V)

Answer

To store visited nodes; it gives O(V^2) regardless

Answer

To randomize node order for fairness

Answer

It does not use a priority queue

Test yourself