Google

The interviewer opened with a multi-pattern string search challenge: "Given a reference text of length n and a dictionary of k keywords of total length m, locate all occurrences of every keyword inside the text in linear time." I explained that running KMP independently for each pattern costs O(k * n + m), while building a naive Trie requires backtracking down branches whenever a mismatch occurs. I pitched the Aho-Corasick Automaton. The interviewer followed up: "Walk me through how you construct the failure transitions and output links, and why scanning the text never backtracks." I explained that we first build a Trie over all dictionary keywords, then use a Breadth-First Search (BFS) to compute failure links—analogous to KMP's LPS array—pointing each node to the longest proper suffix that exists as a valid prefix in the Trie. Crucially, we also compute dictionary/output links that chain terminal keyword matches together so that nested patterns (e.g., "he" inside "she") are collected immediately. During text traversal, the state pointer shifts deterministically through trie edges or falls back via failure links in amortized O(1) steps per text character, finding all matches in optimal O(n + m + occurrences) time and O(m * alphabet) memory. He then shifted to a fast polynomial multiplication scenario: "You have two large polynomials of degree n; compute their product in sub-quadratic time without incurring precision blowup or recursive overhead." I noted that classical schoolbook multiplication takes O(n^2), and while Karatsuba drops it to O(n^1.58), it still hits scaling walls for massive degree bounds. I proposed the Number Theoretic Transform (NTT). The interviewer cut in: "Why choose NTT over standard Fast Fourier Transform (FFT), and what algebraic properties must your chosen modulo satisfy?" I explained that while FFT relies on complex roots of unity ($e^{2\pi i / n}$) which introduce floating-point rounding errors and precision degradation on large integer coefficients, NTT operates entirely within a finite field $\mathbb{Z}_p$, guaranteeing exact integer arithmetic. The prime modulus $p$ must be a Proth prime of the form $c \cdot 2^k + 1$ (such as $998244353$) where $2^k \ge 2n$, ensuring a primitive root $g$ exists whose powers generate primitive $2^k$-th roots of unity modulo $p$. I demonstrated the in-place Cooley-Tukey butterfly operations with bit-reversal permutation, proving the entire convolution executes in strict $O(n \log n)$ time and $O(n)$ space. For the final challenge, he introduced a graph connectivity problem: "Given a directed graph with n vertices and m edges, find the minimum number of directed edges that must be added so that the entire graph becomes strongly connected." I explained that checking reachability naively costs $O(n \cdot (n + m))$ and misses the underlying component structure. I proposed decomposing the graph into Strongly Connected Components (SCCs) using Tarjan’s or Kosaraju’s algorithm. The interviewer challenged me: "Once you condense each SCC into a single supernode to form a Directed Acyclic Graph (DAG), what is the exact formula for the minimum edges required, and what is the single edge-case exception?" I broke down the reduction: in the condensed DAG, every component is classified by its in-degree and out-degree. Let $S_{in}$ be the count of source components (in-degree $= 0$) and $S_{out}$ be the count of sink components (out-degree $= 0$). To make the DAG strongly connected, every source must receive at least one incoming edge and every sink must emit at least one outgoing edge; pairing them up greedily means the minimum edges needed is exactly $\max(|S_{in}|, |S_{out}|)$. As for the edge case, if the initial graph is already strongly connected (condensed into exactly 1 supernode), zero edges are required rather than $\max(1, 1) = 1$. He approved the topological proof, watched me write the condensation and in/out-degree tallying logic, and verified the $O(n + m)$ runtime and memory bounds.