Google

The interviewer opened with an advanced algebraic graph theory and matrix decomposition challenge: "Given an undirected unweighted graph G with n vertices and m edges, compute the exact number of spanning forests of G modulo 998244353 in polynomial time, even if G is disconnected." I noted that Kirchhoff's Matrix Tree Theorem computes the number of spanning trees for a single connected component by taking any cofactor of the graph Laplacian L = D - A, but evaluating cofactors on a disconnected graph yields 0 and fails to count forests. I proposed utilizing the Characteristic Polynomial of the Laplacian matrix via the Jacobi / Binet-Cauchy identity. The interviewer followed up: "Walk me through how the coefficients of the characteristic polynomial det(x * I - L) encode spanning forests of all sizes, and how you evaluate the entire coefficient vector in O(n^3) time." I explained that by the generalized Matrix Tree Theorem, if we express the characteristic polynomial of the graph Laplacian as p(x) = det(x * I - L) = sum_{k=0}^n (-1)^{n-k} c_k x^k, each coefficient c_k equals the sum over all subsets of vertices of size k of the principal minors of L of order n - k. Comb-theoretically, each principal minor of size n - k counts the number of rooted spanning forests with exactly k trees (rooted spanning forests where each tree root is chosen from a distinct component). Specifically, the total number of unrooted spanning forests is given by evaluating the polynomial at x = 1, or by extracting c_k to count forests of fixed component count. To compute the full polynomial det(x * I - L) without symbolic algebra blowup, we transform the symmetric matrix L into tridiagonal (or upper Hessenberg) form via Householder reflections or orthogonal similarity transformations in O(n^3) time. For an upper Hessenberg matrix H, det(x * I - H) can be computed in O(n^2) operations via a 3-term recurrence or Laplace cofactor expansion along rows. This yields all coefficients and the total spanning forest count in strict O(n^3) time and O(n^2) space. He then shifted to a computational geometry and range-searching scenario on rectilinear line segments: "Given n horizontal and m vertical line segments in the 2D plane, count the exact number of pairs of segments that intersect in O((n + m) log(n + m)) time, and adapt it online to report all k intersecting pairs without allocating 2D spatial grids." I pointed out that checking all n * m segment pairs takes quadratic time, which fails when n, m = 10^5. I proposed Bentley-Ottmann's Orthogonal Segment Intersection Sweep-Line using a Fenwick tree (Binary Indexed Tree) for counting, paired with Fractional Cascading or Range Trees for reporting. The interviewer cut in: "A general line sweep must handle event updates when segments cross, but rectilinear sweep lines are simpler. Walk me through the exact event classification, why no new events are dynamically scheduled during the sweep, and how degeneracy (overlapping endpoints and collinear segments) is handled without float errors." I explained that since all segments are strictly horizontal or vertical, intersection points can only occur between a horizontal segment and a vertical segment, meaning segments never change their relative vertical order during the sweep; hence, the event schedule is entirely static. We decompose the input into three types of 1D events sorted by x-coordinate: (1) Start of a horizontal segment [x_1, x_2] at y (insert y into the active structure), (2) End of a horizontal segment at x_2 (remove y from the active structure), and (3) A vertical segment at x spanning [y_1, y_2] (query how many active y-coordinates fall within [y_1, y_2]). To handle collinear endpoints and vertical lines lying exactly at a horizontal segment's boundary, we enforce a strict tie-breaker order on events sharing the same x-coordinate: horizontal start events are processed first, vertical queries second, and horizontal end events last. By compressing the unique y-coordinates of horizontal segments, inserting and deleting active y-coordinates takes O(log n) via a Fenwick tree, while range sum queries in [y_1, y_2] take O(log n). This counts all orthogonal intersections in O((n + m) log(n + m)) time and O(n + m) space. For the final challenge, he introduced an algebraic string and combinatorics on words problem: "Given an arbitrary word w of length n over a finite alphabet, determine whether w is an Abelian Square (a string of the form u v where v is an anagram/permutation of u) in strictly sub-quadratic time, and count all Abelian square substrings in O(n^2 / w_size) or via 4-Russians speedup." I pointed out that checking every even-length substring naively by comparing character frequency histograms takes O(n^3) or O(n^2 * alphabet) time, which chokes on large inputs. I proposed using Multi-Dimensional Prefix Parity Hashing paired with the Four Russians technique or Radix-based Signature Bucketing. The interviewer challenged me: "Two substrings u and v are anagrams if and only if their Parikh vectors (character count vectors) are identical. Walk me through how prefix Parikh vectors transform the search into finding pairs (i, j, k) with Parikh(s[i...j]) = Parikh(s[j+1...k]), and how randomized polynomial hashing reduces the dimension check to O(1)." I broke down the algebraic reduction: we define the Parikh vector of a prefix s[0...t] as P(t) = (cnt_{c_1}(t), cnt_{c_2}(t), ..., cnt_{c_sigma}(t)). A substring s[i...2j - i] is an Abelian square if and only if P(j) - P(i) = P(2j - i) - P(j), which rearranges to 2 * P(j) = P(i) + P(2j - i). To test this condition without maintaining sigma-dimensional vectors, we map each character c_k to a high-degree random polynomial weight or a tuple of large independent primes (r_k, p_k). We define the hash of the Parikh vector as H(P(t)) = sum_{k=1}^sigma cnt_{c_k}(t) * r_k mod M. Because this hash is strictly linear with respect to vector addition, the condition 2 * P(j) = P(i) + P(2j - i) implies the scalar congruence 2 * H(P(j)) = H(P(i)) + H(P(2j - i)) mod M. By stepping the half-length L = j - i and sliding across the text, we check these algebraic balance equations in O(1) expected time. Combining this with 64-bit word-level bit-parallelism (packing letter counts into a single machine word when substring length is bounded) enables testing and counting Abelian squares in O(n^2 / log n) time and O(n) space.