Algorithms, Data Structures, And Complexity Analysis

What's being tested

These questions probe core asymptotic analysis, algorithmic pattern recognition, and practical memory/time accounting for ML workloads: matrix ops, grid propagation, in-memory key-value semantics, vectorized numeric code, and search under API constraints. Interviewers expect clear framing (assumptions + invariants), selection of the right algorithmic template, and honest tradeoff reasoning for production ML pipelines.

Patterns & templates

• Multi-source BFS / wavefront simulation — use queue with visited counts; runs in O(V+E) for grid propagation, handle boundary/threshold updates.

• Naive vs blocked matrix multiply — naive O(n^3); use cache blocking (tile GEMM) and BLAS to approach hardware peak.

• Hash table for KV ops — average O(1) insert/delete; mention load factor, resizing costs, and tombstones for logical deletes.

• NumPy vectorization & broadcasting — prefer `np` vector ops, use `np.broadcast_to` semantics; avoid Python loops to keep O(n) per-element.

• Binary / exponential search under monotonicity — O(log n) if predicate monotonic; if non-monotonic, fall back to linear scan or constrained probing.

• Complexity accounting for ML arrays — size = elements * bytes_per_element (float32 = 4B); factor in temporary arrays for intermediate ops.

• Rate-limited black-box API patterns — memoize calls, batch tests, exponential backoff, and minimize queries by narrowing search space.

Common pitfalls

Pitfall: Confusing algorithmic steps with constant-factor optimizations — saying "use BLAS" isn't a complexity proof; justify asymptotic gains.

Pitfall: Ignoring memory for temporaries — vectorized code can OOM if you create many copies; count peak memory, not just input size.

Pitfall: Assuming monotonicity for binary search — always confirm predicate behavior; binary search on non-monotonic APIs yields wrong answers.