Google

The interviewer opened with an algebraic matching problem on planar graphs: "Given an undirected planar graph G with n vertices, compute the exact number of perfect matchings of G in polynomial time without resorting to exponential #P-complete permanent algorithms." I noted that for general graphs, counting perfect matchings is equivalent to computing the matrix permanent, which is #P-complete (Valiant's theorem). However, for planar graphs, Kasteleyn’s Theorem reduces the permanent to a matrix determinant via a Pfaffian orientation. The interviewer followed up: "Walk me through how a Pfaffian orientation is defined, and explain how face cycles in a planar embedding are oriented so that the determinant det(A) of the skew-symmetric adjacency matrix directly squares to the number of perfect matchings." I explained that a directed orientation of a planar graph is a Pfaffian orientation if for every clockwise traversal of an internal face boundary cycle C, the number of edges oriented in the direction of traversal has odd parity (i.e., is odd). By Kasteleyn’s proof, this parity condition ensures that in the cycle cover expansion of the skew-symmetric adjacency matrix A (where A[u][v] = 1 and A[v][u] = -1 for directed edge u -> v), every superposition of two perfect matchings receives a strictly identical sign (+1), preventing cancellation. To construct this orientation in O(n) time, we compute a spanning tree T of G and fix arbitrary orientations for its edges. We then process faces in a dual tree traversal order: each fundamental cycle contains exactly one non-tree dual edge e, whose direction is deterministically forced to satisfy the odd-parity condition for that face. Once oriented, the Pfaffian Pf(A) equals the exact count of perfect matchings, and since Pf(A)^2 = det(A), we compute det(A) in O(n^3) time (or O(n^(omega/2)) via planar nested dissection) using Gaussian elimination over integers or small primes with Chinese Remainder Theorem, bypassing #P-hardness. He then shifted to an advanced computational geometry and range-searching challenge: "Given n weighted points in the 2D plane and a stream of online queries, where each query provides a triangle Delta and asks for the sum of weights of all points lying inside Delta, answer each query in sub-linear time with O(n) preprocessing space." I pointed out that 2D orthogonal range trees only handle axis-aligned rectangles, and kd-trees have worst-case O(sqrt(n)) query times that degrade under skewed simplicial boundaries. I proposed constructing a Simplicial Range Search Data Structure based on Matoušek's Partition Theorem and Spanning Trees with Low Stabbing Number. The interviewer cut in: "Walk me through how the Partition Theorem recursively divides points, and explain how crossing numbers bound the number of candidate cells intersected by query triangle edges." I explained that by Matoušek’s Partition Theorem, for any set of n points and a parameter r, the plane can be partitioned into t = O(r) simplicial cells Delta_1, ..., Delta_t such that each cell contains at most n / r points, and every arbitrary line crosses the boundary of at most O(sqrt(r)) cells (the low stabbing property). We construct this hierarchy recursively into a partition tree: each internal node stores the bounding simplex of its cell and the aggregate sum of point weights within it. When a query triangle Delta arrives, its boundary consists of three line segments. For each child cell in the current tree level: if the cell lies completely inside Delta, we add its precomputed weight sum in O(1) time without descending; if the cell lies completely outside Delta, it is pruned; if the boundary lines of Delta cross the cell, we recurse into its children. Because each of the 3 boundary lines stabs at most O(sqrt(r)) cells out of r, the recurrence for the query time satisfies T(n) <= 3 * O(sqrt(r)) * T(n / r) + O(1), which solves to O(n^(1/2 + epsilon)) query time using O(n) total space. For the final challenge, he introduced an algebraic string algorithm and suffix sorting structure on compressed data: "Given a run-length compressed string T represented as m runs of characters, construct the Suffix Array of T in O(m log m) time, completely independent of the uncompressed text length n (where n can be 10^18)." I noted that classical suffix array construction algorithms like SA-IS or DC3 operate on raw characters and run in O(n) time, which causes an out-of-memory or time-limit crash when n is astronomically large. I proposed the Block-Distance Run-Sorted Suffix Array construction via Induced Sorting on Run Heads (the Munro-Navarro-Prezza R-SA algorithm). The interviewer challenged me: "When two suffixes share the exact same character run but have different remaining run lengths, their relative lexicographical order isn't purely determined by the next run; walk me through the break-point invariants and how sorting run heads handles periodicity." I broke down the reduction: any suffix starting inside a run of character c can be represented as c^k followed by the suffix starting at the next run boundary. The crucial insight is that within a single run (c, L), suffixes with larger remaining lengths k are not necessarily lexicographically larger or smaller—the order depends on whether the character c' of the subsequent run is greater than or less than c. If c' > c, then c^k < c^{k+1}, meaning longer suffixes within the same run are lexicographically larger; if c' < c, longer suffixes are lexicographically smaller. Thus, the suffixes within a single run form a monotonic chain whose internal relative order is fixed. This means we only need to sort the m suffix endpoints corresponding to the start of each run (the run heads). We define a reduced alphabet of size m where each run is treated as a meta-character with its length and next-run transition encoded into a tuple. We apply a modified SA-IS or Farach-style recursive induced sorting over these m run-head tuples in O(m log m) time. Once the permutation of run heads is established, all intermediate suffixes within each run are interpolated into their fractional positions in O(1) time per run, yielding the fully evaluated compressed suffix array without decompressing a single character of the 10^18 stream.