Google

The interviewer opened with an advanced combinatorial matching challenge on non-metric multigraphs: "You are given a multigraph G with n vertices and m edges where each vertex v has an integer capacity constraint b_v; find a subgraph H such that every vertex has degree exactly b_v in H (the b-factor problem) in polynomial time, without expanding the multigraph into exponential dummy vertices." I noted that naively replacing each vertex v of degree d_v with a bipartite gadget of b_v and d_v - b_v vertices blows up the vertex set to O(m), causing Tutte's reduction to Blossom matching to run in O(m^3) time, which chokes on dense multigraphs. I proposed reducing the b-factor problem directly to Maximum Weight Bipartite/General Matching using the Tutte-Lovasz b-Matching Blossom reduction or the Gabow b-Matching Algorithm. The interviewer followed up: "Walk me through how Gabow's algorithm generalizes Edmond's blossoms into b-blossoms, and what degree-sum invariant defines an alternating blossom cycle when vertices hold arbitrary capacities." I explained that a b-blossom is an odd cycle C of vertices where the sum of capacities sum_{v in C} b_v is odd, meaning that in any valid b-factor, at least one edge of C must be partially unmatched or external. Instead of alternating single edges, an alternating walk alternates between 'deficient' edges (where current flow < lower bound) and 'surplus' edges. When a b-blossom is identified during the alternating search tree expansion, we contract the entire cycle C into a single pseudo-vertex with an adjusted effective capacity b_C = floor((sum_{v in C} b_v - |E(C)|) / 2). Edmonds-style dual potentials are maintained on both original vertices and nested blossom contractions. Upon augmenting flow, contracted blossoms are recursively unpacked and their internal cycles are alternatingly shifted in O(|C|) time. This resolves the general b-factor problem in O(b(V) * E log V) or O(V * E log(V^2 / E)) time using Fibonacci heaps and priority-queue dual adjustments, staying strictly polynomial. He then shifted to an online metric space and streaming cluster-maintenance problem: "Given an infinite stream of points arriving one by one in a d-dimensional Euclidean space, maintain an online set of k cluster centers such that the maximum distance from any point seen so far to its assigned cluster center is at most a constant factor times the optimal offline k-center radius (the online k-center problem)." I pointed out that the optimal offline k-center problem is NP-hard to approximate within any factor strictly less than 2, and an online algorithm cannot predict where future dense point clusters will arrive. I proposed Charikar's Doubling Algorithm (or the Feder-Greene Online Radius Doubling Scheme). The interviewer cut in: "How does the doubling algorithm maintain candidate clusters across exponentially expanding guesses of the optimal radius R, and what geometric invariant guarantees an O(1) competitive ratio?" I explained that the algorithm maintains a candidate radius estimate R. At the start, R is set to the distance between the first two distinct points. For a fixed guess R, we maintain a set of active cluster centers C. When a new point p arrives: we measure its distance to all current centers in C. If min_{c in C} dist(p, c) <= 2 * R, p is absorbed into its closest center and C remains unchanged. If min_{c in C} dist(p, c) > 2 * R, point p is added to C as a brand new cluster center. If the size of C exceeds k + 1 centers, our current guess R is proven mathematically to be too small to cover the stream within optimal radius R* (since k + 1 points separated by > 2 * R cannot be covered by k balls of radius R). We double our guess R = 2 * R and consolidate the existing centers: we run an independent offline greedy set cover on the current k + 1 centers with the new threshold 2 * R, which reduces the center count back down to at most k. Repeating this ensures that at all times, R <= 2 * R*, and the maximum distance from any stream point to its center is bounded by 8 * R*, achieving an 8-competitive online approximation in O(k * d) time per point and O(k * d) space. For the final challenge, he introduced an algebraic combinatorial matrix problem on tournament digraphs: "Given a tournament graph T with n vertices (a directed graph where every pair of vertices has exactly one directed edge between them), find a directed Hamiltonian cycle in T if one exists, and determine whether the adjacency matrix satisfies the Landau Tournament Score Theorem in O(n log n) time." I noted that finding a directed Hamiltonian cycle in a general directed graph is NP-complete, but by Camion's Theorem, every strongly connected tournament graph is guaranteed to contain a directed Hamiltonian cycle. The interviewer challenged me: "Walk me through how Landau's conditions check the out-degree sequence via prefix sums in O(n log n) time, and how an incremental insertion sort constructs a directed Hamiltonian cycle in O(n^2) without backtracking." I broke down the two stages: first, let s_1 <= s_2 <= ... <= s_n be the sorted out-degree sequence (score sequence) of the tournament. Landau's Theorem states that a sequence represents a valid tournament if and only if for all k from 1 to n - 1, the prefix sum satisfies sum_{i=1}^k s_i >= k * (k - 1) / 2, with strict equality when k = n. Sorting the scores and validating these prefix sums runs in O(n log n) time. Second, to construct the Hamiltonian cycle: we first construct a directed Hamiltonian Path v_1 -> v_2 -> ... -> v_n using an insertion-sort divide-and-conquer in O(n log n) comparisons. If the tournament is strongly connected, v_n must have a path back to v_1. Let v_k be the latest vertex in the path that has a directed edge back to v_1 (v_k -> v_1). If k == n, the cycle v_1 -> v_2 -> ... -> v_n -> v_1 is immediately closed. If k < n, by strong connectivity, there must exist some vertex v_i (with i <= k) that has a directed edge to some vertex v_j (with j > k). We splice the subpath v_{k+1} -> ... -> v_n into the cycle between v_i and v_{i+1}, expanding the cycle to cover all n vertices. Repeating this splicing step consumes each remaining node in O(n) steps, guaranteeing the explicit construction of the Hamiltonian cycle in strict O(n^2) deterministic time and O(n) space.