Google

The interviewer opened with an advanced algebraic graph theory scenario: "Given an undirected unweighted graph G with n vertices and m edges, determine whether the graph contains a directed/undirected triangle-free cycle of length at least 4 in polynomial time, or more specifically, compute the exact size of the minimum cycle basis (MCB) of G in sub-cubic time without running independent all-pairs shortest paths." I noted that extracting cycle bases naively via Horton's algorithm requires generating O(m * n) candidate fundamental cycles and sorting them before running Gaussian Elimination over GF(2), which costs O(m^2 * n^2) or O(m^3 * n) time—far too slow when n reaches 2000. I proposed the Mehlhorn-Michail / Kavitha Fast Minimum Cycle Basis Algorithm using isometric cycle candidates and signed edge incidence over GF(2). The interviewer followed up: "Walk me through how Horton's candidate cycle set C(v, e) = dist(v, u) + (u, w) + dist(w, v) is pruned down to an essential basis without testing all vertices v, and how linear independence is maintained over GF(2)." I explained that any cycle in a minimum cycle basis must be isometric—meaning for any two vertices on the cycle, one of the two connecting paths on the cycle is a shortest path in G. Instead of testing all n possible apex vertices v for each edge e = (u, w), we only consider vertices where the sum of distances dist(v, u) + dist(v, w) + 1 is minimal. To maintain linear independence without a full O(m^3) matrix elimination, we maintain a dual basis of witness vectors S_1, S_2, ..., S_{m - n + c} over GF(2) that are orthogonal to the cycle space. For each candidate cycle C, we evaluate its dot product with the current witness vector in O(m / 64) using bitsets. If the dot product is 1, C is linearly independent of the current basis; we add C to our MCB, update the remaining witness vectors via rank-1 updates, and advance. This drops the total construction time to O(m^2 * n / log n) with O(m * (m - n)) bitset memory. He then shifted to a computational geometry and kinetic physical simulation challenge: "You are given n moving particles on a 1D line, where each particle i has a continuous trajectory x_i(t) = x_0 + v_i * t with constant velocity v_i; maintain the exact convex hull (upper envelope) of particle positions as a dynamic data structure over continuous time t in [0, infinity) without discrete time-stepping." I pointed out that discrete time-stepping (delta_t) either misses critical collision/passing events or suffers from catastrophic numerical lag. I proposed a Kinetic Tournament / Kinetic Data Structure (KDS) maintaining an upper envelope. The interviewer cut in: "Walk me through how certificates define the validity of the current combinatorial structure, and how certificate failure events are scheduled in an event queue." I explained that a KDS maintains two things: the attribute (here, the upper envelope represented by the sequence of particles that currently form the top convex chain) and a set of elementary geometric certificates whose conjunction proves the attribute remains correct. For an upper envelope, the certificate for adjacent particles i and j on the hull asserts that particle i is higher than particle j before their intersection time, and the intersection time with the next particle k occurs in valid sequence (convexity turn condition). For each certificate, we solve the algebraic equation x_i(t) = x_j(t) to compute the exact future failure time t_fail. These failure timestamps are pushed into a global Priority Queue. When the simulation clock jumps to the earliest t_fail, only the local certificate is violated: we swap the positions of i and j in our upper envelope, discard their outdated neighbor certificates, compute the failure times for the new adjacent pairs, and insert the new certificates into the priority queue. Because trajectories are linear, any two lines intersect at most once, bounding the total number of combinatorial changes to O(n * alpha(n)) events, each handled in O(log n) time and O(n) space. For the final challenge, he introduced an algebraic combinatorics and polynomial-roots problem: "Given an integer n up to 10^5 and an arbitrary sequence of n points (x_1, y_1), (x_2, y_2), ..., (x_n, y_n) over a finite field Z_p, compute the unique interpolating polynomial P(x) of degree strictly less than n such that P(x_i) = y_i for all i in strictly sub-quadratic O(n log^2 n) time." I observed that classical Lagrange Interpolation requires computing O(n) basis polynomials, which takes O(n^2) operations, and Newton's divided differences also requires O(n^2) time, both of which fail completely when n exceeds 5000. I proposed Fast Multipoint Evaluation and Interpolation via Subtree Polynomial Trees and NTT. The interviewer challenged me: "Walk me through the divide-and-conquer tree layout, explain why the derivative of the vanishing polynomial M'(x) appears in the denominator, and how the values M'(x_i) are computed in sub-quadratic time." I broke down the algebraic reduction: let M(x) = product_{i=1}^n (x - x_i) be the master polynomial. By L'Hopital's rule on Lagrange's formula, the coefficient of each term simplifies to y_i / M'(x_i), where M'(x) is the formal derivative of M(x). We first construct a binary Subproduct Tree where each leaf stores (x - x_i) and each internal node stores the polynomial product of its children, computed using NTT in O(n log^2 n) time; the root yields M(x). We compute the formal derivative M'(x) in O(n) time. To find all n values M'(x_i) simultaneously without running n independent Horner evaluations, we run Fast Multipoint Evaluation: starting at the root of the subproduct tree with polynomial M'(x), we descend the tree, replacing the polynomial at each child with its remainder modulo that child's subtree polynomial (using fast polynomial division via Newton inversion in O(k log k)). At the leaves, each node contains the exact value M'(x_i). Finally, we reverse up the tree, recombining partial fractions P_left * M_right + P_right * M_left using NTT. Across log n tree levels, every level performs O(n log n) operations, completing the entire polynomial interpolation in strict O(n log^2 n) time and O(n log n) space.