Algorithm Design and Analysis Questions

Covers algorithmic problem solving and analysis fundamentals required in technical interviews. Topics include common data structures, sorting and searching, recursion and divide and conquer, dynamic programming, greedy strategies, backtracking, graph algorithms such as breadth first search and depth first search, shortest path and topological sort, string algorithms, and techniques for deriving correct and efficient solutions. Candidates should demonstrate ability to reason about correctness, derive time and space complexity bounds using Big O notation, and discuss scalability and optimization trade offs for large inputs.

MediumSystem Design

157 practiced

Design an algorithm to compute the top-k most frequent feature values across a distributed dataset of categorical features (e.g., top k product categories). The dataset is sharded; describe a map-reduce style approach and analyze communication cost and memory per worker.

Sample Answer

Requirements & assumptions:- Input: categorical feature values across N shards (workers). Want global top-k by frequency.- Constraints: large cardinality, limited memory per worker, minimize network traffic and latency. Exact vs approximate: prefer exact if counts per distinct value fit aggregator; otherwise allow approximate (provable error).

High-level MapReduce approach (exact counts):1. Map (local counting + combiner): each worker scans its shard and builds a local hashmap count[value] (or uses an on-disk/streaming map if huge). Then emit only (value, count_local) for values present. Use a combiner to aggregate duplicates before shuffle.2. Shuffle: partition keys by hash to R reducers so each reducer gets counts for a subset of values.3. Reduce: each reducer sums counts for its assigned values to produce global count per value. Finally reducers compute their local top-k and send them to a coordinator.4. Final aggregation: coordinator merges R sorted top-k lists (using a min-heap of size k) to produce global top-k.

Communication cost (exact):- Let M be number of distinct (value, per-shard) pairs emitted after combining. Worst-case M = sum over shards of distinct values per shard; in worst-case equals total occurrences (bad). Typical: M ≈ U_avg * N where U_avg is average unique values per shard.- Data sent over network equals size of all emitted (value, count) pairs: O(M * (key_size + count_size)). Using combiners reduces M significantly.Memory per worker:- Mapper: needs memory to hold local hashmap of distinct values in shard. Memory = O(U_local * avg_key_size). If U_local too big, spill to disk or use a streaming heavy-hitter algorithm.- Reducer: needs memory to aggregate counts for keys assigned to it: O(U_reducer). Final merge needs O(k) at coordinator.

Optimizations & approximate alternatives:- Use combiner aggressively to reduce shuffle.- Use partitioning that balances reducer load (range/hashing) and handle skew (sample keys to choose partitions).- If U is huge, use approximate streaming algorithms per shard: - Count-Min Sketch (CMS): small fixed memory, gives approximate counts with error bounds; then merge sketches across workers (additive) and query top-k with additional heavy-hitter structure. - SpaceSaving / Frequent algorithm: per-shard keep top-(k*α) heavy hitters; emit only those to reduce M; guarantees top-k recovery for heavy items.- Use hierarchical aggregation: local top-L -> intermediate aggregators -> final merge to reduce bandwidth.

Trade-offs:- Exact approach ensures correctness but can be expensive in network and memory for high-cardinality features.- CMS/SpaceSaving reduce memory and communication at controlled accuracy loss.- Combiner + sampling + load-aware partitioning mitigate skew and cost.

Recommendation for ML engineer:- If downstream requires exact counts for feature engineering (e.g., deterministic feature indices), provision reducers with enough memory and use combiners and skew mitigation.- If approximate is acceptable (e.g., for feature selection), use SpaceSaving per shard or mergeable CMS for bounded-memory, fast aggregation.

HardTechnical

90 practiced

Create an algorithm to compress a large embedding table for production inference using quantization and pruning. Outline an approach combining k-means-based vector quantization and sparse pruning; describe encoding, lookup-time cost, accuracy trade-offs, and how to evaluate the impact on end-to-end ML metrics.

Sample Answer

Requirements & goals:- Reduce RAM/disk and memory-bandwidth for large embedding table (N rows × D dims) with minimal end-to-end metric loss (CTR, recall, etc.), fast lookup for inference.

Approach (pipeline):1. Preprocess: L2-normalize or scale embeddings per-table to stabilize k-means and pruning.2. Vector quantization (k-means): - Partition D into P subspaces (product / PQ-style) or cluster full vectors depending on D and latency. - For each partition, run k-means (K centroids). Replace each subvector by centroid index. Store centroids in compact float16 or float32. - Encoding: each row stores P indices (log2 K bits each) → compressed codebook. Total storage ≈ N·P·log2K bits + P·K·D/P·4 bytes. - Lookup-time cost: reconstructing full embedding requires P centroid lookups and concatenation: O(P) random accesses + O(D) additions; or use asymmetric distance/product lookup optimizations to avoid full reconstruction.3. Sparse pruning: - Train/finetune with L1 magnitude-aware or structured pruning (column/block or per-dimension pruning) to zero small weights. Use gradual magnitude pruning with retraining or knowledge-distillation to recover accuracy. - Store sparse indices (CSR) or bitmask per row. Combine with quantization by pruning first to reduce cluster variance.4. Hybrid storage/serving: - Hot-cold: keep top-M frequent ids fully dequantized in memory; cold ids remain compressed on SSD/NVM with on-demand decode. - Use fused kernels: centroid-gather + mask-apply to produce final embedding without full float reconstruction when possible.

Trade-offs:- K increases → better accuracy, more bits/latency. P (more subspaces) reduces centroid size but may increase quantization error.- Aggressive pruning yields sparsity & compute reduction but can remove signal causing ML metric drop. Structured pruning reduces lookup overhead vs unstructured.

Performance & cost:- Storage reduction factor ≈ (original N·D·32 bits) / (N·P·log2K + centroid storage + sparse index overhead).- Latency: per-lookup ≈ P random centroid reads + sparse mask application; aim for P small (4–16) and K power-of-two for bit ops.- Memory bandwidth reduced roughly proportional to compression ratio; CPU/GPU compute shifts to centroid gathers.

Evaluation (end-to-end):- Offline: measure reconstruction MSE and cosine similarity per-id; evaluate downstream metrics (AUC, CTR, recall@K) on validation set with A/B style shadow runs.- Online: A/B test with key business metrics, latency P95, and throughput; monitor model calibration and fairness.- Robustness: test cold-start IDs, distribution shifts, and tail-frequency IDs.- Iteration: sweep (K,P,prune rate,hot-M) to build Pareto frontier of accuracy vs latency vs size; use constrained optimization (minimize size subject to metric loss < δ).

Notes:- Prefer retraining/finetuning after quant+prune with teacher embeddings to close gap.- Use quantization-aware training or product quantization-aware loss when possible to minimize end-to-end degradation.

EasyTechnical

137 practiced

Explain what the 'curse of dimensionality' means for nearest neighbor search and density estimation. Provide mathematical intuition and concrete examples of when increasing dimensionality degrades distance-based algorithms used in ML pipelines.

Sample Answer

The "curse of dimensionality" describes how many intuitions and methods that work in low dimensions break down as feature dimension d grows — for nearest-neighbor (NN) search and density estimation this is mainly about volume explosion and distance concentration.

Mathematical intuition- Volume: the volume of a d-ball of radius r scales ∝ r^d. To capture a fixed fraction of probability mass, the radius must grow as r ∝ mass^(1/d). For high d this radius approaches the whole space, so neighborhoods become huge.- Distance concentration: for many distributions (e.g., isotropic Gaussian or uniform in [0,1]^d) pairwise distances concentrate — the relative contrast (max distance − min distance) / min distance → 0 as d increases. Concretely, if x ∼ Uniform[0,1]^d, E[||x||^2]=d/12 and std( ||x|| ) grows much slower, so distances between points are nearly equal.

Implications- Nearest-neighbor search: because distances are similar, the nearest neighbor is not much closer than a random point; NN labels/noisy estimates become unreliable; exact NN search is expensive because tree partitioning (KD-tree) degrades and becomes linear.- Density estimation: kernel density estimators require bandwidths that scale badly with d; to get sufficient samples in a local neighborhood you need exponentially many points (sample complexity ∝ ε^{-d} for fixed error ε).

Concrete example- Uniform points in [0,1]^d: to have an expected nearest-neighbor distance r with n samples, r ≈ (log n / n)^{1/d}. With fixed n, r quickly approaches 0.5 as d grows — neighborhoods cover most of the cube.

Practical mitigations- Dimensionality reduction (PCA, autoencoders, random projections with Johnson–Lindenstrauss)- Feature selection / domain-specific embeddings- Use similarity measures or models that exploit structure (cosine similarity for sparse high-dim text)- Approximate NN (LSH, ANNOY, FAISS) and metric learning to improve contrast.

This explains why distance-based components in ML pipelines must be treated carefully as dimensionality rises.

HardTechnical

90 practiced

Provide a proof or argument showing why comparison-based sorting requires Omega(n log n) comparisons in the worst case. Then explain why radix sort can run in O(n) under certain conditions and when it's applicable for ML preprocessing (e.g., sorting fixed-length integer feature buckets).

HardSystem Design

104 practiced

Design an algorithm to perform approximate nearest neighbor (ANN) search for high-dimensional embeddings (e.g., 512-d vectors) at billion-scale. Describe trade-offs between exact search, KD-trees, product quantization, and locality-sensitive hashing. Provide a high-level architecture for an ML inference service that answers ANN queries with <50ms latency.

Sample Answer

Requirements & constraints:- Query p95 latency <50 ms, throughput thousands qps, dataset ~1B vectors (512-d), recall target (e.g., 0.9), update frequency (offline vs streaming), cost/memory constraints.

Trade-offs (exact vs ANN methods):- Exact brute-force: PCA/BLAS + dot-products / FAISS GPU brute-force — highest recall (100%) but O(N·d) compute; impractical at billion-scale for <50ms unless large GPU clusters & batching (costly).- KD-trees: work well for low-d (<30). For 512-d they suffer from curse of dimensionality — tree degenerates, high probe counts → poor latency/recall trade-off.- Locality-Sensitive Hashing (LSH): Hash-based sublinear retrieval; simple and parallelizable. Good for cosine/L2 but needs many hash tables to reach high recall → memory and IO cost; results can be unstable; simpler to implement for disk-backed indexes.- Product Quantization (PQ) + IVF (inverted file): Compress vectors into compact codes, partition dataset into coarse clusters (IVF) then scan only top cells using PQ distance lookup — excellent memory footprint and recall/latency trade-offs. Often used in FAISS for billion-scale.- Graph-based (HNSW): Builds small-world graph over vectors; very high recall and low latency, good for high-d; memory heavy (edge pointers) but faster than PQ for many workloads. Harder to update at scale but supports excellent recall-latency.

High-level architecture (<50ms p95):1. Offline pipeline: - Feature store: store original embeddings and metadata (S3/Bigtable). - Index builder: use FAISS/ScaNN to build multi-stage index (IVF-PQ or hybrid IVF-PQ + HNSW coarse quantizer). Partition dataset into shards (consistent hashing / range). - Export compact indices to object store and distribute to serving nodes.

2. Serving layer (per-region, autoscaled): - Sharded index replicas: each node holds one shard in RAM (or GPU memory for high QPS). Use hybrid index: IVF for low memory + PQ for compression; optionally HNSW on centroids for faster routing. - Query router/gateway: receives query, normalizes embedding, routes to subset of shards (top-k routing or all shards depending on recall). Use async fan-out with configurable fanout to meet recall/latency budget. - Per-shard search process: perform coarse search (IVF) → PQ distance compute (SIMD) → local top-K → optional re-rank with original float vectors (if kept) to improve recall. - Aggregator: merge top-K results from shards, apply final rerank, return results. - Caching: LRU cache for hot queries and embeddings; result caching for repeated queries. - GPU/CPU balance: use GPU instances for latency-critical heavy queries (batching small groups with 5–10 ms amortized cost) and CPU SIMD optimized code for others.

Operational concerns:- Sharding & replication: replicate shards (N replicas) for availability/latency; use consistent re-sharding with minimal data movement.- Index updates: batch rebuilds for large-scale; delta-buffer of recent vectors in small in-memory index (real-time) merged periodically.- Metrics & tuning: track recall, latency per component, CPU/GPU utilization. Provide configurable search parameters: nprobe (IVF), PQ bytes, ef/search (HNSW) to tune recall vs latency.- Libraries & infra: FAISS, ScaNN, Milvus, or proprietary C++ services; deploy in k8s with nodePools (GPU/CPU), use gRPC for low-latency RPC, CDN for client geo-distribution.

Summary of trade-offs:- Choose IVF-PQ when memory and storage cost must be minimized at billion scale; tune nprobe and PQ bits to hit recall/latency.- Choose HNSW when highest recall + lowest latency is required and memory budget allows.- LSH is an option for simpler deployments or when probabilistic guarantees suffice.- Exact search only with heavy GPU investment or for small candidate sets that require perfect recall.

This design provides flexible knobs (nprobe/ef/compaction) so you can meet <50ms by trading memory, CPU/GPU, and recall.

Unlock Full Question Bank

Get access to hundreds of Algorithm Design and Analysis interview questions and detailed answers.

Join thousands of developers preparing for their dream job.