Google

The interviewer opened with an advanced algebraic graph theory and reachability challenge: "Given an arbitrary directed acyclic graph (DAG) G with n vertices and m edges, compute the size of the transitive closure (the number of reachable pairs (u, v)) in sub-cubic time, and approximate the reachability count within (1 +- epsilon) in nearly-linear time." I noted that running transitive reduction or Floyd-Warshall/DFS from each node requires O(n * (n + m)) = O(n * m), which hits 10^10 operations for n, m = 10^5. I proposed using Cohen’s Min-Hash Algorithm on DAGs (Reachability Sketches). The interviewer followed up: "Walk me through how assigning uniform random ranks from [0, 1] to vertices transforms set cardinality estimation into finding minimum path values, and how dynamic programming propagates these sketches in topological order." I explained that for each vertex v, let R(v) denote the set of all vertices reachable from v. If we assign independent uniform continuous random variables r(u) ~ Uniform(0, 1) to all vertices u in V, the minimum value among reachable nodes, X_v = min_{u in R(v)} r(u), is distributed as the minimum of |R(v)| independent uniform variables. The expected value of this minimum is strictly E[X_v] = 1 / (|R(v)| + 1), which directly yields the estimator |R(v)| approx (1 / X_v) - 1. Because G is a DAG, we evaluate X_v for all vertices in a single reverse topological sweep: X_v = min(r(v), min_{(v, w) in E} X_w), processing every edge exactly once in O(n + m) time. To reduce variance and guarantee an epsilon-relative error with high probability, we repeat this trial k = O(log n / epsilon^2) times using independent hash functions, tracking the k smallest values (Bottom-k sketch) or averaging the estimators. Propagating the k-dimensional sketch vectors across the DAG in reverse topological order evaluates all reachability sizes in strict O((n + m) * (log n / epsilon^2)) time and O(n * (log n / epsilon^2)) space. He then shifted to a computational geometry and kinetic dynamic partition problem: "Given n point masses moving along linear trajectories in the 2D plane p_i(t) = s_i + v_i * t, design a data structure that maintains the Delaunay Triangulation of the moving points continuously over time, and bound the number of discrete topological modifications (edge flips) that occur." I pointed out that periodically re-running Fortune’s or Bowyer-Watson algorithms at fixed time steps wastes CPU cycles on quiescent trajectories and introduces discrete sampling errors. I proposed maintaining a Kinetic Delaunay Triangulation (KDT) governed by In-Circle Certificate Failures. The interviewer cut in: "A Delaunay triangulation is uniquely certified by local empty-circumcircle tests on adjacent triangle pairs; write down the algebraic in-circle determinant, explain its degree as a polynomial in t, and show how a topological flip restores the Delaunay property when a certificate fails." I broke down the algebraic certificate mechanics: for two adjacent triangles sharing an internal edge e = (a, b) with opposing outer vertices c and d, the edge e is locally Delaunay at time t if and only if d lies outside the circumcircle of triangle (a, b, c). This condition is evaluated by the sign of the 4x4 parabolic lifting determinant: det([[x_a(t), y_a(t), x_a(t)^2 + y_a(t)^2, 1], [x_b(t), y_b(t), x_b(t)^2 + y_b(t)^2, 1], [x_c(t), y_c(t), x_c(t)^2 + y_c(t)^2, 1], [x_d(t), y_d(t), x_d(t)^2 + y_d(t)^2, 1]]) > 0. Because each coordinate x_i(t) and y_i(t) is a linear polynomial in t, the lifted coordinate x_i(t)^2 + y_i(t)^2 is quadratic in t. Expanding the 4x4 determinant produces a polynomial in t of degree at most 2 + 1 + 1 = 4. The real roots of this quartic equation greater than the current time t_now represent the exact future instants when points a, b, c, and d become cocircular. We schedule the earliest valid root for each internal edge into an event priority queue. When the top event fires at time t_event, the certificate fails: the four vertices form a convex quadrilateral whose diagonal e = (a, b) is replaced by the alternate diagonal (c, d) via a local edge flip in O(1) time. We then remove the obsolete certificates of the affected neighboring triangles, compute the roots of the newly created triangles, and push them into the queue. The total number of topological flips across all time is bounded by O(n^(2 + epsilon)), allowing continuous maintenance in O(log n) time per topological event. For the final challenge, he introduced an algebraic string structure on two-dimensional text arrays: "Given a 2D text matrix T of size n x n and a 2D pattern matrix P of size m x m over an alphabet, find all occurrences of P in T in optimal O(n^2) deterministic time, parameterized independently of pattern dimension m." I noted that naive 2D template matching takes O(n^2 * m^2), and independent 2D FFT cross-correlations take O(n^2 log n), which fails the strict linear-time O(n^2) bound. I proposed the Bird / Baker 2D String Matching Algorithm combining the Aho-Corasick Automaton with the Knuth-Morris-Pratt (KMP) failure function. The interviewer challenged me: "Walk me through how 2D matching decomposes into 1D row-level equivalence classes, and how the vertical sweep tracks column transitions without storing full 2D prefixes." I broke down the two-phase pipeline: in the first phase, we extract the m distinct row patterns of the pattern matrix P: R_1 = P[0, :], R_2 = P[1, :], ..., R_m = P[m-1, :]. We insert these m strings into an Aho-Corasick string matching automaton, where each distinct row string is assigned a unique integer state identifier ID in {1, 2, ..., m}. We then scan every row of the text matrix T through this Aho-Corasick automaton: for each cell T[i][j], the automaton reports in O(1) which pattern row ends at column j. This transforms the original 2D character matrix T into an intermediate 2D integer matrix of row identifiers M where M[i][j] = ID(P_k) if P[k] matches ending at T[i][j], and 0 otherwise. In the second phase, notice that the entire 2D pattern P is uniquely represented as a vertical 1D sequence of identifiers: S_P = [ID(R_1), ID(R_2), ..., ID(R_m)]. A full 2D match ending at cell T[i][j] occurs if and only if the vertical column slice M[i - m + 1 ... i][j] equals the sequence S_P. We compute the standard KMP failure function (pi array) over the 1D identifier array S_P in O(m) time. Then, as we sweep down each column j from i = 0 to n - 1, we feed the sequence M[i][j] into the KMP automaton, maintaining an active match state `kmp_state[j]` for each column. Whenever `kmp_state[j] == m`, an exact 2D occurrence of P is confirmed ending at (i, j). Because Aho-Corasick processes the n^2 text cells in O(n^2) and KMP processes the column streams in O(n^2), the total algorithm runs in strict O(n^2 + m^2) time and O(m^2 + n) space.