Google

The interviewer opened with an advanced linear algebra and randomized polynomial identity problem: "You are given a directed graph G with n vertices and m edges; determine whether the graph contains a directed Hamiltonian cycle in randomized polynomial time without resorting to O(2^n * poly(n)) subset dynamic programming." I noted that the directed Hamiltonian cycle problem is NP-complete, meaning no deterministic polynomial-time algorithm is known. However, if parameterized or algebraic testing is allowed, we can reduce cycle detection to computing the non-zeroness of a symbolic polynomial using the Bjorklund-Husfeldt Algebraic Algorithm via the Tutte-Berge polynomial and Exterior Algebra (Grassmann / Clifford Algebra) over GF(2). The interviewer followed up: "Grassmann exterior algebras feature anti-commutative basis products (e_i ^ e_j = -e_j ^ e_i and e_i ^ e_i = 0); explain how this nilpotent property annihilates non-simple walks while preserving Hamiltonian cycles." I explained that any standard matrix walk counts closed walks that may revisit vertices. If we decorate each edge (u, v) with a basis generator e_v from a Grassmann algebra, the weight of a walk v_1 -> v_2 -> ... -> v_k is the exterior product e_{v_1} ^ e_{v_2} ^ ... ^ e_{v_k}. If a walk revisits any vertex v_i, the product contains e_{v_i} ^ e_{v_i} = 0, which automatically vanishes. Thus, all self-intersecting walks collapse to zero, leaving only simple paths and cycles. By mapping the trace of the exterior adjacency matrix power A^n over a truncated exterior algebra of degree n, the resulting coefficient is non-zero if and only if a Hamiltonian cycle exists. He verified the nilpotent basis cancellation and acknowledged the reduction to algebraic matrix identity testing. He then shifted to a computational geometry and convex polygon intersection query engine: "Given two convex polygons P and Q with n and m vertices respectively, compute their intersection polygon in optimal O(n + m) time without falling back on generic O((n + m) log(n + m)) sweep-line segmentation." I pointed out that Bentley-Ottmann line sweep takes O((n + m + k) log(n + m)), which is suboptimal because it fails to exploit the strict convexity of P and Q. I proposed the O'Rourke / Shamos Plane-Sweep Directional Vector Algorithm. The interviewer cut in: "Walk me through how the two directional edge vectors chase each other around the perimeters, and what cross-product rules govern pointer advancement." I broke down the chasing mechanics: we maintain two directed edge pointers, A on polygon P and B on polygon Q, along with their outward-pointing normal vectors. At each step, we compute whether directed edge A points into the half-plane of edge B (via the 2D cross product of vector A and vector B, cross(A, B)). If cross(A, B) > 0 and B's head lies to the left of A's line, we advance pointer A; otherwise, if cross(B, A) > 0 and A's head lies to the left of B's line, we advance pointer B. Whenever the current segments A and B physically intersect, we compute the intersection point in O(1) and append it to our output vertex list. If the pointer advancing next is currently inside the other polygon, its destination vertex is also appended. Because each step advances at least one edge pointer along its convex boundary without retreating, the loop terminates after at most 2 * (n + m) iterations, constructing the intersection polygon in strict O(n + m) time and O(n + m) space. For the final challenge, he introduced an algebraic string algorithm and period-structure problem: "Given a string s of length n, compute the runs of s—all maximal periodic substrings (tuples of the form (start, end, period) with exponent >= 2)—in strict O(n) deterministic time." I noted that the Main-Lorentz divide-and-conquer algorithm finds runs in O(n log n) time, while achieving strict O(n) requires deep structural periodicity via Lyndon words. I pitched the Crochemore-Rytter / Kolpakov-Kucherov Algorithm based on Lyndon Factorization. The interviewer challenged me: "According to the Runs Theorem, the total number of runs in any string is strictly less than n. How does Duval's Lyndon factorization over two opposite character orderings guarantee isolating all runs in linear time?" I explained that any run with minimal period p contains an internal Lyndon factor of length p with respect to some total ordering of the alphabet <=. By running Duval's algorithm twice—once under the standard lexicographical ordering <=_0 and once under the reversed ordering <=_1—we decompose s into Lyndon trees in O(n) time. Each run's shortest period p appears as a node in one of these two Lyndon factor trees. Once the candidate periods p and their boundaries are extracted from the Lyndon trees, we extend them to their maximal left and right periodic boundaries using Longest Common Extension (LCE) queries. By precomputing the Suffix Array with an RMQ-based LCP array or using Suffix Automata, each LCE query executes in O(1) time. Pruning duplicate runs via a 64-bit rolling hash or tuple set keeps the entire extraction within strict O(n) total time and O(n) auxiliary space.