Google

The interviewer opened with an algebraic graph theory and lattice geometry problem on topological graph invariants: "Given an undirected simple graph G with n vertices and m edges, compute the Colin de Verdière Invariant mu(G)—the topological dimension parameter that characterizes whether G is outerplanar (mu <= 2), planar (mu <= 3), or linklessly embeddable in R^3 (mu <= 4)—by casting it as an optimization problem over symmetric matrices and the Strong Arnold Property (SAP)." I observed that testing for graph minors (like Robertson-Seymour minor testing for Petersen family obstructions in linkless embedding) incurs massive galactic constants. I proposed computing mu(G) directly via Semidefinite Programming (SDP) and Transversality Verification of Matrix Manifolds. The interviewer followed up: "State the three structural axioms defining a Colin de Verdière matrix M in R^{n x n}, and explain how the Strong Arnold Property prevents trivial rank deficiencies by enforcing transversality against the manifold of symmetric matrices of fixed corank." I explained that a symmetric real matrix M in S_n belongs to the Colin de Verdière family for G if: (1) for all distinct vertices i != j, M[i][j] < 0 if (i, j) in E, and M[i][j] = 0 if (i, j) not in E; (2) M has exactly one negative eigenvalue (of multiplicity 1); and (3) M satisfies the Strong Arnold Property: if X is a symmetric matrix such that M * X = 0 and X[i][j] = 0 whenever i = j or (i, j) in E, then X must be identically the zero matrix. The invariant is defined as mu(G) = max corank(M) over all such matrices M. The SAP condition is an algebraic transversality condition: it guarantees that the affine space of matrices respecting the graph's non-edge sparsity pattern intersects the manifold of matrices of rank n - corank(M) transversally at M. To evaluate this computationally, we formulate the search for M as a rank-minimization problem subject to Linear Matrix Inequalities (LMIs): M + t * e_1 e_1^T >= 0 for an appropriate rank-1 perturbation to ensure exactly one negative eigenvalue. Using an Interior-Point Barrier SDP solver, we locate the boundary of the spectrahedral cone. At a candidate solution M, checking the SAP reduces to verifying that the linear system M * X = 0 subject to X_{E \cup diag} = 0 has a trivial kernel, which is resolved via standard Gaussian elimination over the vec(X) matrix of size O(n^2) in polynomial time, establishing mu(G). He then shifted to a computational geometry and kinetic dynamic partition problem: "Given n stationary points in R^3 in general position, preprocess the point cloud to answer Upper Envelope / Extreme Point queries—given an online query plane H: z = a*x + b*y + c, determine whether all n points lie strictly below H, and if not, return the point with the maximum vertical distance above H—in O(log n) time, while maintaining the 3D Convex Hull under a sequence of point insertions in O(log^2 n) amortized time per insertion." I noted that static 3D convex hulls can be computed in O(n log n) via Preparata-Hong or Chan's randomized incremental algorithm, but dynamic point insertions typically degrade the hull structure or force O(n) re-triangulation cascades across the faceted surface. I proposed using the Overmars-van Leeuwen Dynamic 3D Convex Hull combined with Dobkin-Kirkpatrick Hierarchical Polyhedral Decompositions. The interviewer cut in: "A dynamic 3D convex hull cannot easily maintain planar facial complexes explicitly in polylogarithmic time; walk me through how Chan's Randomized Hierarchical Framework or the Dobkin-Kirkpatrick hierarchy resolves extreme point queries via logarithmic-depth nested polyhedra." I explained that we maintain a sequence of nested polyhedral approximations P_0 \supset P_1 \supset ... \supset P_k, where P_0 is the full 3D convex hull and each P_{i+1} is formed by removing a maximal independent set of low-degree vertices (degree at most 8) from the boundary of P_i and re-triangulating the resulting holes in O(1) time per vertex. Because an independent set of bounded-degree vertices on a planar surface graph contains a constant fraction of vertices (at least |P_i| / c), the hierarchy has depth k = O(log n). To find the extreme point in direction v = (-a, -b, 1), we start at the coarsest polyhedron P_k (which has O(1) vertices) and find its extreme vertex v_k in O(1) time. When moving from P_{i+1} to P_i, the extreme vertex of P_i is guaranteed to be either v_{i+1} or one of the independent vertices removed in the hole adjacent to v_{i+1}. Because each hole has bounded degree, local inspection takes O(1) operations per level, descending through all O(log n) levels in strict O(log n) total query time. To support insertions, we wrap this hierarchical structure in a Bentley-Saxe logarithmic decomposition over powers of two, rebuilding subtrees when sizes balance, which yields O(log^2 n) amortized insertion time and O(n) total space. For the final challenge, he introduced an algebraic string structure and two-dimensional sequence scenario: "Given an arbitrary string s of length n, preprocess s to answer Non-Overlapping Substring Indexing queries: given two indices [i, j] and [k, l] defining two substrings u = s[i...j] and v = s[k...l], find the maximum number of mutually non-overlapping occurrences of u and v packed consecutively as alternating blocks (u v u v ...) in s, in time parameterized strictly by the count of occurrences rather than text length n." I noted that finding all occurrences of u and v naively using a Suffix Tree takes O(|u| + |v| + occ) time, but computing the maximum non-overlapping alternating sequence is a variant of interval scheduling that naively sorts and scans all occurrence positions, taking O(occ * log(occ)) time. I proposed using Heavy-Light Decomposition (HLD) over the Suffix Tree paired with Orthogonal Range Maximum / Successor Queries in a Persistent Segment Tree. The interviewer challenged me: "Walk me through how the loci of u and v in the Suffix Tree map their occurrences to 1D index intervals, and how dynamic fractional cascading or predecessor queries find the next non-overlapping valid block in O(log log n) time per hop." I explained that we build the Suffix Tree of s in O(n) time. The substring u corresponds to an implicit or explicit node locus Node(u), and its occurrences are precisely the leaf indices stored in the subtree rooted at Node(u). Using the DFS entry and exit timestamps of the suffix tree leaves, the occurrence positions of u correspond to values falling within a contiguous range in the Suffix Array SA[L_u ... R_u], and similarly for v within SA[L_v ... R_v]. The greedy choice for packing alternating blocks u and v is optimal: given an occurrence of u ending at position p, we must select the earliest occurring instance of v that starts at an index q >= p + 1. Once that v ending at position q + |v| - 1 is chosen, we find the earliest instance of u starting at index r >= q + |v|, and so forth. Finding the earliest occurrence of a substring in a text window [t_start, n] whose SA index lies in [L, R] is a 2D Range Successor Query: find the smallest text index pos in [t_start, n] such that the suffix position pos has rank(pos) in [L, R]. We index the suffix array positions using a Persistent Segment Tree over text coordinates. Each jump to the next alternating block evaluates one range successor query in O(log n) time (or O(log log n) via a Van Emde Boas-augmented range tree). If the maximum alternating chain has length k, we trace the greedy chain in O(k log n) time, resolving the non-overlapping packing in time proportional to the output chain size k rather than the total occurrences of u or v.