Computer Science Basics for ML Engineers: What the Interview Actually Tests
Published:
Why an ML role asks these questions at all
Because the job is mostly not modelling. The slow thing is almost never the matrix multiply — it is the Python loop that rebuilds a list every step, the in check against a list instead of a set, the tokeniser that concatenates strings quadratically. Those are complexity bugs wearing an ML costume.
And cost has to be predicted, not measured: a six-hour run on eight GPUs cannot be profiled casually. You are expected to see a nested loop over a dataset and say “that is quadratic, it will not finish” before launching it.
What is being graded
Interviewers are not checking whether you memorised heapsort, but four separable things:
- Cost reasoning. You say “expected \(O(n \log n)\)”, not just “\(n \log n\)”. Being precise about which case you are quoting is the clearest signal of someone who has done this for real.
- Container instinct. The problem says “have I seen this before”, and your hand types a
setwithout deliberation. Most interview problems are one data-structure choice away from trivial. - Boundary correctness. Binary search, sliding windows, two pointers, tree recursion — short and unforgiving; a correct one written calmly beats a clever one that is off by one.
- Runtime awareness. Why threads do not speed up a CPU-bound Python loop, why a default argument mutated across calls, why appending is cheap and inserting at the front is not.
The eight posts
| Post | The question it answers |
|---|---|
| Complexity and big-O | What does \(O\) actually claim, how do you read a cost off nested loops and off recursion, and when does the asymptotically better algorithm lose? |
| Arrays and hashing | Why contiguity beats pointer-chasing, why appending is amortised \(O(1)\), and why “hash tables are \(O(1)\)” is three qualifications short of true. |
| Stacks, queues, heaps | LIFO and FIFO and what they buy you; the array-as-tree trick that makes a heap; why building one is linear. |
| Trees and BSTs | The four traversals and what each is for; why an unbalanced BST is a linked list with extra steps; what balancing guarantees. |
| Graphs and traversal | List versus matrix; BFS versus DFS; topological order; Dijkstra and the assumption it silently makes; union-find. |
| Sorting and searching | Binary search without off-by-one errors; the three \(n\log n\) sorts and their different failure modes; why \(\Omega(n \log n)\) is a theorem, and how to beat it legally. |
| Recursion and DP | Base cases and the call stack; memoisation versus tabulation; the two conditions that make DP apply, and a fully filled edit-distance table. |
| Memory and concurrency | Stack versus heap; reference semantics in Python; reference counting and cycles; threads, the GIL, and why data loaders fork processes. |
They are ordered as a path: complexity is the vocabulary, the data-structure posts are the nouns, the algorithm posts are the verbs, and the last post is the machine everything runs on. Under time pressure, read the complexity post properly and skim the rest — every other post states its claims in that language.
The one table to have memorised
Average case unless marked. \(n\) is the number of elements held.
| Operation | Dynamic array | Hash table | Balanced BST | Binary heap |
|---|---|---|---|---|
| Lookup by key | — | \(O(1)\), \(O(n)\) worst | \(O(\log n)\) worst | — |
| Lookup by index | \(O(1)\) worst | — | — | — |
| Insert | \(O(1)\) amortised at the end, \(O(n)\) in the middle | \(O(1)\) amortised | \(O(\log n)\) worst | \(O(\log n)\) worst |
| Delete | \(O(n)\) | \(O(1)\) amortised | \(O(\log n)\) worst | \(O(\log n)\) worst (min only) |
| Min | \(O(n)\) | \(O(n)\) | \(O(\log n)\) worst | \(O(1)\) worst |
| Ordered iteration | sort first | not available | \(O(n)\) worst | sort first |
No column wins everywhere: the hash table gives up order, the heap gives up everything except the minimum, the array gives up cheap insertion in the middle. Interview problems are usually built so that exactly one column fits.
while lo <= hi but updated with hi = mid loops forever. (4) A mutable default argument such as def f(x, seen=[]) is created once at function definition and shared by every call.How to use this book
Read for the derivations, not the facts. Every complexity claim is labelled worst, average or amortised, and short derivations are given in full. Code is Python throughout, because that is what you will be asked to write and because several sharp edges — reference semantics, the GIL, list.pop(0) — are Python-specific. Related maths lives in the maths basics book, and the graph post connects to the graph neural network book.
Recap
- Four things are graded: precise cost claims, container instinct, boundary correctness, runtime awareness. Everything else is decoration.
- Always attach a case to a complexity: worst, average, or amortised. "\(O(1)\)" alone is not a complete answer for a hash table or a dynamic array.
- No container dominates. Hash tables trade away order, heaps trade away everything but the extremum, arrays trade away cheap middle insertion — pick against the operation mix.
- Predicting cost matters more than measuring it, because ML jobs are too expensive to profile by launching them.
- Three derivations cover most whiteboard proofs: the geometric series for amortised append, \(\log_2(n!) = \Theta(n\log n)\) for the sorting bound, and \(\sum_h h/2^h = 2\) for linear build-heap.
References
- Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. Introduction to Algorithms, 4th ed. MIT Press, 2022.
- Sedgewick, R., & Wayne, K. Algorithms, 4th ed. Addison-Wesley, 2011.
- Knuth, D. E. The Art of Computer Programming, Vol. 3: Sorting and Searching, 2nd ed. Addison-Wesley, 1998.
- Python Software Foundation. TimeComplexity — Python Wiki.
- Python Software Foundation. The Python Standard Library.