Google

The interviewer opened with an advanced algebraic graph theory and polyhedral optimization challenge: "Given an undirected simple graph G with n vertices and m edges, determine whether G is a Chordal Bipartite Graph in strict O(m * sqrt(n)) or linear time, and construct its doubly lexical ordered bipartite adjacency matrix to solve the Maximum Weight Independent Set on G in polynomial time without general integer programming." I noted that while Maximum Independent Set is NP-hard on general bipartite graphs, chordal bipartite graphs possess a totally balanced adjacency matrix, which makes the independent set polytope completely integral. I proposed recognizing the class via Lexicographic Breadth-First Search (Lex-BFS) on the bipartite double cover or Rose-Tarjan-Lueker elimination orderings. The interviewer followed up: "Walk me through how a doubly lexical ordering of the bipartite adjacency matrix eliminates Gamma-submatrices (induced 2x2 identity matrices), and how dynamic programming or greedy dual rounding extracts the maximum independent set in O(n + m) time." I explained that a bipartite graph is chordal bipartite if every cycle of length 6 or greater has a chord (meaning it contains no induced C_{2k} for k >= 3). We construct an ordered bipartite adjacency matrix A where rows represent U and columns represent V. By running Paige-Tarjan doubly lexical ordering (iterative partition refinement on rows and columns), we permute A such that it contains no Gamma configuration—a submatrix where A[i_1, j_1] = 1, A[i_1, j_2] = 1, A[i_2, j_1] = 1, and A[i_2, j_2] = 0 for indices i_1 < i_2 and j_1 < j_2. A bipartite matrix is totally balanced if and only if it admits such a Gamma-free ordering. Lubiw proved that on a totally balanced matrix, the greedy algorithm for fractional packing and covering yields integral extreme points: traversing vertices in the reverse of the doubly lexical elimination ordering, we greedily select vertices into the independent set while dropping their closed neighborhoods. This resolves the Maximum Weight Independent Set on chordal bipartite graphs in O(n + m) time after an O(m log n) or O(m * sqrt(n)) recognition phase. He then shifted to a computational geometry and kinetic dynamic partition problem: "Given n weighted points in the 2D plane and a stream of online queries, each specifying an arbitrary query segment s, compute the Lower Envelope of the arrangement of n segments in O(n log n) time, and design a data structure that answers Ray-Shooting queries from an interior point downward to find the first segment hit in O(log^2 n) time, bounding the storage to O(n alpha(n))." I pointed out that the lower envelope of n line segments has worst-case combinatorial complexity Theta(n * alpha(n)) (a Davenport-Schinzel sequence of order 3), so building a full 2D trapezoidal decomposition over the entire segment arrangement wastes O(n^2) space on hidden crossings. I proposed constructing the Lower Envelope via Divide-and-Conquer Merge with Segment Trees of Partial Functions. The interviewer cut in: "Walk me through why the intersection of two lower envelopes of size n_1 and n_2 can be merged in O((n_1 + n_2) * alpha(n_1 + n_2)) time, and how an augmented Interval Tree answers downward ray-shooting queries without planar point location." I broke down the divide-and-conquer envelope pipeline: we partition the n segments into two halves of size n/2, recursively compute the lower envelope of each half, and merge them. Each recursive envelope is an x-monotone step-and-segment function. Merging two such envelopes E_1 and E_2 requires finding all mutual intersection points. Since any two line segments intersect at most once, the cross-over sequence of segments between E_1 and E_2 forms a Davenport-Schinzel sequence of order 3, whose length is bounded by O((|E_1| + |E_2|) * alpha(|E_1| + |E_2|)). We perform a simultaneous left-to-right sweep across the x-intervals of E_1 and E_2, finding local crossings in O(1) time per segment pair. The recurrence T(n) = 2 * T(n/2) + O(n * alpha(n)) solves to O(n * alpha(n) * log n) construction time. For downward ray-shooting, we store the resulting envelope segments in an Interval Tree indexed by their x-spans. When a query ray shoots down from point (x_q, y_q), we isolate the O(log n) tree nodes covering x_q, evaluate the y-coordinate of each candidate segment at x = x_q in O(1) time, and pick the highest segment lying strictly below y_q. This answers each downward ray-shooting query in strict O(log n) time using O(n * alpha(n)) space. For the final challenge, he introduced an algebraic combinatorics and topological data structures problem on graphs: "Given a connected graph G with n vertices and m edges, compute the exact Rank of its Cycle Matroid M(G) and determine whether the graph admits a Nowhere-Zero 4-Flow (Tutte's 4-Flow Conjecture for graphs without Petersen minors), constructing such a flow in O(m) time if G is 3-edge-connected and planar." I noted that a Nowhere-Zero k-flow is the dual equivalent of a proper k-vertex coloring on planar graphs. Tutte proved that a planar graph admits a nowhere-zero 4-flow if and only if its planar dual G* is 4-vertex colorable (the Four Color Theorem). The interviewer challenged me: "Bypassing the Four Color Theorem's complex computer reductions, explain how Jaeger's 8-Flow and 4-Flow theorems use two disjoint spanning trees to synthesize nowhere-zero flows algebraically over the Klein four-group Z_2 x Z_2." I explained that a nowhere-zero 4-flow is algebraically isomorphic to assigning non-zero group elements from the Klein four-group Z_2 x Z_2 = { (0, 0), (0, 1), (1, 0), (1, 1) } to directed edges such that the net group sum entering every vertex equals (0, 0). Jaeger proved that a graph admits a nowhere-zero 4-flow if and only if its edge set can be partitioned into two spanning Eulerian subgraphs (subgraphs with all even vertex degrees). If G is 4-edge-connected (or 3-edge-connected without certain obstructions), by the Nash-Williams / Tutte Tree Packing Theorem, G contains two edge-disjoint spanning trees T_1 and T_2. Let C_1 = G \setminus E(T_1) and C_2 = G \setminus E(T_2). Because T_1 and T_2 are edge-disjoint, C_1 and C_2 together cover all edges of G. For any tree T, the fundamental cycle basis allows us to construct an Eulerian subgraph E_i whose edges outside T match any designated parity. We construct an even-degree subgraph H_1 by taking the fundamental cycles of T_1 needed to correct odd degrees, and similarly construct an even-degree subgraph H_2 from T_2. We then define the vector flow function f(e) = (chi_{H_1}(e), chi_{H_2}(e)) in Z_2 x Z_2, where chi_H(e) = 1 if edge e in H, and 0 otherwise. Because H_1 and H_2 have even degrees at every vertex, Kirchhoff’s flow conservation holds modulo 2 independently in both coordinates. Because T_1 and T_2 are edge-disjoint, every edge belongs to at least one of H_1 or H_2, which guarantees that f(e) != (0, 0) for all edges e. This produces an explicit nowhere-zero 4-flow in strict O(m * alpha(m)) deterministic time and O(m) space.