Google

The interviewer opened with an algebraic matching problem on non-bipartite graphs: "Given an arbitrary unweighted undirected graph G with n vertices and m edges, determine whether G has a perfect matching, and if so, construct the actual matched pairs in polynomial time using linear algebraic inversions rather than Edmond's Blossom contractions." I noted that the classical Blossom algorithm contracts odd cycles (blossoms) in O(V * E) or O(V^2.376) time, but can be error-prone to implement under competition time limits. I proposed the Rabin-Vazirani Randomized Algebraic Matching Algorithm using the inverse of the Tutte matrix over a finite field. The interviewer followed up: "We know the symbolic determinant of Tutte's skew-symmetric matrix T is non-zero if and only if a perfect matching exists. How do you find the actual edge pairings from the numerical inverse of T in O(n^3) time without recalculating the full determinant after each matched pair?" I explained that we substitute random values from a large finite field Z_p into T and compute its numerical inverse matrix T_inv = T^(-1) in O(n^3) time via Gaussian elimination. By Jacobi's identity, an edge (u, v) belongs to a perfect matching if and only if entry T_inv[u][v] != 0. To construct the matching, we search for an edge (u, v) where T_inv[u][v] != 0, add (u, v) to our matching, and eliminate vertices u and v from the graph. Crucially, we do not recompute the entire matrix inverse from scratch; instead, we perform a rank-2 Sherman-Morrison-Woodbury update on T_inv to condition out rows and columns u and v in O(n^2) time. Repeating this across n/2 pairing steps constructs the entire perfect matching in strict O(n^3) time and O(n^2) space. He then shifted to an advanced string periodicity and grammar index: "Given a string s of length n, construct the Run-Length Burrows-Wheeler Transform (RLBWT) and build an index (r-index) that supports counting and locating all occ occurrences of any query pattern p of length m in O(m log log n + occ) time, using space proportional only to the number of runs r in the BWT of s (where r << n)." I pointed out that standard FM-indexes sample suffix array positions every k characters, requiring O(n / k) space which still scales with text length n, exhausting memory on repetitive collections like genomic databases where n is 10^11 but r is only 10^6. I proposed the Gagie-Navarro-Prezza r-index. The interviewer cut in: "Walk me through how the LF-mapping works over compressed run blocks, and how sampling suffix array values strictly at run boundaries allows locating all matches without full suffix arrays." I explained that the BWT of a highly repetitive string clusters into r equal-character runs. We represent the BWT using a run-length encoded vector: characters C_k and run lengths L_k, supported by a predecessor data structure (like an Elias-Fano or wavelet tree) to evaluate LF-mapping (L[i] to F[i]) in O(log log n) time. For counting, backward search using LF-mapping computes the range [sp, ep] of BWT rows matching pattern p in O(m log log n) time. For locating, we store the explicit Suffix Array values SA[i] only at the first and last position of each of the r runs in the BWT. If a query interval [sp, ep] contains any run boundary, we read its precomputed SA sample directly; for any other row in [sp, ep], tracing LF-mapping forward along the run preserves the relative distance to the run's boundary. Thus, we reconstruct the exact text positions of all occurrences without expanding the full suffix array, keeping the index size bounded to strict O(r) words. For the final challenge, he introduced an algebraic spectral graph and tree-packing theorem: "Given an undirected unweighted graph G with n vertices and m edges, compute its Effective Resistance matrix and construct an (1 + epsilon)-Spectral Sparsifier H with only O(n log n / epsilon^2) edges in nearly-linear time, such that for all vectors x, the Laplacian quadratic forms satisfy (1 - epsilon) * x^T L_G x <= x^T L_H x <= (1 + epsilon) * x^T L_G x." I noted that traditional spanners preserve shortest-path graph distances, but can completely destroy cut capacities, electrical flows, and spectral eigenvalues. I proposed the Spielman-Srivastava Algorithm using Effective Resistance edge sampling. The interviewer challenged me: "Define effective resistance R_eff(e) using the Moore-Penrose pseudoinverse of the graph Laplacian, and explain how the Johnson-Lindenstrauss lemma allows approximating R_eff for all edges in O(m log n) time." I explained that treating the graph as an electrical resistor network where each edge has 1-ohm resistance, the effective resistance across edge e = (u, v) is R_eff(u, v) = (chi_u - chi_v)^T L^+ (chi_u - chi_v), where L^+ is the Moore-Penrose pseudoinverse of the graph Laplacian L and chi_u is the indicator basis vector. Spielman and Srivastava proved that sampling edges independently with probability proportional to their leverage scores p_e = w_e * R_eff(e) produces a spectral sparsifier of size O(n log n / epsilon^2). Computing L^+ directly takes O(n^3), which fails for large networks. However, by running the Spielman-Teng or LapLACIAN fast linear system solver, we compute Z = L^+ * Q, where Q is a random projection matrix with O(log n / epsilon^2) rows. By the Johnson-Lindenstrauss Lemma, the Euclidean distances between the projected node vectors in Z preserve all edge effective resistances within (1 +/- epsilon) with high probability. This estimates all p_e values and constructs the certified spectral sparsifier in O(m log^c n / epsilon^2) time and O(m) space.