Google

The interviewer opened with an advanced algebraic graph theory and lattice flow problem: "Given an undirected network G with n vertices and m integer-capacitated edges, compute the exact number of spanning trees whose Laplacian tree-level potential is an integral vector, or more specifically, compute the Smith Normal Form (SNF) of the Graph Laplacian L and find the invariant factors of the graph's Sandpile Group (Jacobian Group) Jac(G) in polynomial time." I noted that finding the size of the Sandpile Group |Jac(G)| is simply evaluating the cofactor of the Laplacian via Kirchhoff's Matrix Tree Theorem, but discovering its full isomorphic group decomposition Jac(G) = Z_{d_1} x Z_{d_2} x ... x Z_{d_{n-1}} (where d_i divides d_{i+1}) requires finding the diagonal Smith Normal Form of the reduced Laplacian L_red. The interviewer followed up: "Computing the SNF of an integer matrix by raw row and column gcd eliminations can trigger exponential coefficient bit-length growth (intermediate entry explosion); how do you guarantee polynomial bit-complexity during diagonalization?" I explained that the reduced Laplacian L_red is an (n-1) x (n-1) symmetric, strictly diagonally dominant M-matrix. Instead of unbounded integer pivots, we compute the SNF using Kannan-Bachem's or Storjohann's modular reduction framework. First, we compute the determinant det(L_red) = |Jac(G)| via Gaussian elimination over a sequence of small primes and reconstruct the integer determinant via the Chinese Remainder Theorem; let this scalar determinant be Delta. Because all invariant factors d_i must divide Delta, all subsequent row and column operations (unimodular transformations) are carried out modulo Delta. In each elimination phase, to reduce an off-diagonal entry L[i][j] against pivot L[i][i], we compute the extended Euclidean gcd: a * L[i][i] + b * L[i][j] = g, multiply by the 2x2 unimodular transformation [[a, b], [-L[i][j]/g, L[i][i]/g]], and immediately reduce all entries modulo Delta. This keeps every intermediate integer strictly bounded within [0, Delta - 1] (at most O(n log n) bits). Diagonalizing the matrix across n - 1 steps recovers the invariant factors d_1, d_2, ..., d_{n-1} in O(n^3 * log^2(Delta)) bit-operations and O(n^2 log Delta) space. He then shifted to a computational geometry and kinetic dynamic partition problem: "Given n stationary points in the 2D plane and a parameter k <= n, construct an Order-k Voronoi Diagram—partitioning the plane into convex regions such that all points inside a single cell share the exact same set of k nearest neighbors among the n points—in O(k * (n - k) * log n + n log^3 n) time, without constructing all (n choose k) subsets." I pointed out that naively testing all (n choose k) combinations is impossible, while intersecting half-spaces for each subset takes exponential time. I proposed building the Order-k Voronoi Diagram by slicing through the 3D Convex Hull (or Upper Envelope) of 2D points lifted onto a Paraboloid via Levels in Hyperplane Arrangements. The interviewer cut in: "Walk me through how the geometric duality transforms k-nearest neighbors into the k-th level of a 3D plane arrangement, and explain how topological peeling or Clarkson-Shor randomized sampling constructs the diagram in optimal time." I broke down the algebraic lifting and duality: each point P_i = (x_i, y_i) in the plane is lifted to a tangent plane to the unit paraboloid z = x^2 + y^2, given by H_i: z = 2 * x_i * x + 2 * y_i * y - (x_i^2 + y_i^2). The Euclidean distance from a query point q = (x, y) to site P_i is monotonically related to the vertical distance from the paraboloid point (x, y, x^2 + y^2) down to the plane H_i. Therefore, the k sites closest to q correspond to the k lowest planes at coordinates (x, y). The boundaries of the Order-k Voronoi cells are the vertical projections onto the xy-plane of the edges forming the k-th level of the 3D arrangement of the n planes H_1, ..., H_n (where a point is on the k-th level if exactly k - 1 planes lie strictly below it). By the Clarkson-Shor sampling technique or Lee's iterative peeling algorithm, the k-th level is constructed by updating the (k - 1)-th level: adjacent cells in Order-(k - 1) differ by replacing one nearest site. We trace the changes across levels using a circular sweep along the Voronoi edges. Because the total combinatorial complexity of the k-th level in a 3D arrangement of n planes is strictly bounded by O(k * (n - k)), the entire Order-k diagram is generated in O(n k log n) time and O(k * (n - k)) space. For the final challenge, he introduced an algebraic string structure and non-local periodicity problem: "Given a string s of length n, find its Shortest Unique Palindromic Substring (SUPS) for all indices—meaning for every character position i in s, find the shortest substring containing s[i] that is both a palindrome and occurs exactly once in s—in strict O(n) deterministic time." I noted that the set of all palindromes can be O(n^2), and querying suffix trees or Palindromic Trees (Eertree) naively for each position takes quadratic time. I proposed using an augmented Palindromic Tree (Eertree) paired with Suffix Automaton frequency queries and a Segment Tree of Palindromic Intervals. The interviewer challenged me: "According to Droubay, Justin, and Pirillo, any string of length n contains at most n distinct palindromic substrings. How does the Eertree identify unique palindromes, and how do you distribute their coverage over positions in linear time?" I explained that the Eertree constructs at most n + 2 nodes in O(n) time, where each node u represents a distinct palindromic substring P_u. For each node u in the Eertree, we determine whether P_u is unique in s (occurs exactly once) by inspecting the size of its end-position set; in an Eertree, during construction, we record the occurrence count of each node by propagating counts upward along suffix links from the leaves in O(n) time. A node u is a unique palindrome if and only if its occurrence count is exactly 1. For every unique palindromic node u of length L_u with its unique starting position [start, start + L_u - 1], this palindrome covers every index i in [start, start + L_u - 1]. To find the shortest such palindrome for all positions i simultaneously without an interval segment tree that adds log n overhead, we utilize two linear passes: First, for each position i, the candidate unique palindrome of minimum length can be tracked via difference arrays on intervals: we record the length L_u at the boundary and propagate values across the string, or use the fact that the answer function ans[i] satisfies a Lipschitz condition |ans[i] - ans[i+1]| <= 2. By sweeping left-to-right and right-to-left while maintaining the shortest active palindromic window using a monotone queue or Disjoint Set Union (DSU) to skip indices that already have smaller assignments, all n position answers are resolved in strict O(n) deterministic time and O(n) space.