Google

The interviewer opened with an advanced shortest-path query scenario on planar topologies: "Given a planar undirected graph G with n vertices and non-negative edge weights, design a data structure that answers point-to-point shortest path queries between any two arbitrary vertices in sub-linear time per query, with sub-quadratic preprocessing time and memory." I pointed out that running Dijkstra on the fly requires O(n log n) per query, while all-pairs shortest paths (APSP) requires O(n^2) space and time, which is completely intractable when n reaches 10^5. I proposed using planar graph separators to construct a Recursive Voronoi / FR-Dijkstra Hierarchical Decomposition (Fakcharoenphol-Rao structure). The interviewer followed up: "Walk me through how the Planar Separator Theorem recursively partitions the graph, and explain how the Monge property of boundary-to-boundary distance matrices allows searching without relaxing all edges." I explained that by the Lipton-Tarjan Planar Separator Theorem, any planar graph can be split into two disconnected subgraphs of size at most 2n/3 by removing a separator of size O(sqrt(n)) in O(n) time. Repeating this recursively yields a division into regions with O(r) interior vertices and O(sqrt(r)) boundary vertices. Crucially, if you order the boundary vertices along the outer face of a region in cyclic order, the distance matrix between boundary vertices satisfies the Monge condition (cross-inequality: dist(a, c) + dist(b, d) <= dist(a, d) + dist(b, c)). This Monge property enables FR-Dijkstra to maintain shortest path intervals and locate the next minimum-distance boundary node using the SMAWK algorithm or a recursive matrix search in O(B log^2 B) rather than standard O(B^2) edge relaxations. As a result, the distance hierarchy supports exact shortest path queries in O(n^(1/2) * poly(log n)) time with O(n log n) space. He then shifted to string search and compressed pattern matching: "Given a text T of length n compressed via Run-Length Encoding into m runs (where m can be exponentially smaller than n), and a raw pattern P of length k, count the exact occurrences of P in T in time parameterized by m and k, without decompressing T into its full n characters." I noted that fully decompressing T requires Omega(n) memory and time, which instantly invalidates the query if n is on the order of 10^12 while m is only 10^5. I proposed reducing the problem to an augmented string matching automaton using KMP/Aho-Corasick on run-blocks with interval boundary testing. The interviewer cut in: "Walk me through the three structural cases when matching run-compressed text: what happens if P spans across runs, and how do you handle internal runs where a character repeats thousands of times?" I broke down the cases: first, if the pattern P consists of only a single run (e.g., 'a' repeated k times), an occurrence happens inside any text run (c_i, len_i) where c_i == 'a' and len_i >= k, contributing exactly len_i - k + 1 matches via simple arithmetic. Second, if P consists of two runs, we check every adjacent pair of text runs using closed-form prefix-suffix bounds. Third, if P has three or more runs, we split P into three parts: a prefix run P_pre = (c_0, l_0), a sequence of exact middle runs P_mid = [(c_1, l_1), ..., (c_{r-1}, l_{r-1})], and a suffix run P_suf = (c_r, l_r). The middle runs P_mid must match the compressed text runs as an exact contiguous sequence of (character, length) tuples. We search for P_mid inside the compressed text runs using the standard KMP algorithm over run-tuples in O(m + |P_mid|) time. Whenever KMP finds a valid match for the middle runs starting at text run i, we check the flanking text runs: text run i - 1 must have character c_0 and length >= l_0, and text run i + r must have character c_r and length >= l_r. Each such match generates exactly 1 valid occurrence. Thus, all matches are counted in strict O(m + k) time and O(m + k) space. For the final challenge, he introduced an algebraic spectral graph theory problem: "Given an undirected unweighted d-regular graph G with n vertices, determine whether G is an expander graph—specifically, estimate its edge expansion ratio h(G) = min_{|S| <= n/2} (|E(S, V \ S)| / |S|) within a provable factor in polynomial time without checking all 2^n subsets." I explained that computing the exact edge expansion h(G) is NP-hard, equivalent to finding the sparsest cut. However, by Cheeger's Inequality from spectral graph theory, we can bound and approximate the expansion using the second-smallest eigenvalue of the graph Laplacian. The interviewer challenged me: "Walk me through how the normalized Laplacian is constructed, state Cheeger's inequality relating lambda_2 to h(G), and describe how the Fiedler vector is used to construct a sparse cut." I explained that for a d-regular graph, the normalized Laplacian is L = I - (1/d) * A, where A is the adjacency matrix. The eigenvalues of L are 0 = lambda_1 <= lambda_2 <= ... <= lambda_n <= 2. Cheeger's Inequality establishes that (d * lambda_2) / 2 <= h(G) <= sqrt(2 * d^2 * lambda_2). To extract an explicit cut, we compute the eigenvector corresponding to lambda_2 (the Fiedler vector v) using the Power Iteration method or the Lanczos algorithm in O(m / sqrt(lambda_2)) time. We then sort all vertices based on their coordinate values in the Fiedler vector: v_{p_1} <= v_{p_2} <= ... <= v_{p_n}. We sweep through the n candidate prefix sets S_k = {p_1, ..., p_k} for 1 <= k <= n/2, computing the conductance |E(S_k, V \ S_k)| / (d * |S_k|) for each prefix cut in O(m) total time. Cheeger's constructive rounding proof guarantees that the best prefix cut among these n candidates achieves an expansion within the Cheeger bound, providing a polynomial-time approximation without combinatorial enumeration.