Google

The interviewer opened with an advanced linear programming and structural duality problem: "Given a general undirected graph G with n vertices and m edges, find the maximum weight of an independent set in polynomial time, assuming G is bipartite." I pointed out that finding a Maximum Weight Independent Set (MWIS) is NP-hard for general graphs, but for bipartite graphs, the problem reduces to Maximum Weight Bipartite Matching and Minimum Cut via Konig's Theorem and linear programming duality. The interviewer followed up: "Walk me through how you transform MWIS into a Minimum Cut (s-t cut) network flow problem, and how the min-cut partition directly yields the optimal independent set." I explained that we introduce a virtual source S and sink T. Every left vertex u in partition L receives a directed edge from S with capacity equal to its weight w(u), and every right vertex v in partition R sends a directed edge to T with capacity w(v). For every original undirected edge (u, v) in the bipartite graph, we insert a directed edge from u to v with capacity infinity. Because these cross-edges have infinite capacity, any finite s-t cut can never sever them, meaning the cut cannot select both u on the S-side and v on the T-side if edge (u, v) is violated. An element is retained in the independent set if it is NOT cut: specifically, left vertices on the S-side of the cut and right vertices on the T-side of the cut form the independent set. By the Max-Flow Min-Cut Theorem, the minimum cut capacity equals the minimum weight of vertices that must be excluded to eliminate all edges, meaning Total_Weight - Min_Cut strictly equals the Maximum Weight Independent Set. He had me code the Dinic's network setup and confirmed the O(V^2 * E) bound. He then shifted to an offline array query problem featuring two-dimensional monotonic constraints: "Given an array of n integers and q offline queries asking for the maximum value in range [L, R] of (nums[i] ^ nums[j]) such that L <= i < j <= R, answer all queries in sub-quadratic time." I noted that answering each query by checking all pairs inside [L, R] takes O(q * N^2) naively, and a standard Binary Trie cannot filter both left and right boundary constraints simultaneously. I proposed combining a Persistent 0-1 Trie with Divide and Conquer over Queries or Monotonic Stack Point Reduction. The interviewer cut in: "Explain how to reduce the number of candidate pairs (i, j) across the entire array from O(N^2) to O(N log(max_val)) before processing the range queries." I broke down the reduction: for any index j, we want to find indices i < j that maximize nums[i] ^ nums[j]. We maintain a Persistent 0-1 Trie where version t contains the elements nums[0...t]. For index j, instead of searching the whole prefix, we query the trie to find the best match in sub-intervals, or we leverage the property that across bit positions b from 30 down to 0, there are at most O(log(max_val)) critical indices i < j that can ever form an optimal XOR pair with j. Each such critical pair (i, j) with value v = nums[i] ^ nums[j] generates a 2D point (i, j) with weight v. A range query [L, R] then asks for the maximum weight among all generated points satisfying x >= L and y <= R. This is an offline 2D Orthogonal Range Maximum Query, which we solve in O((N log(max_val) + q) log N) by sorting events by y and querying an auxiliary Segment Tree over x. He approved the point reduction and verified the memory bounds. For the final challenge, he introduced a graph clustering and spectral graph theory scenario: "Given an undirected weighted graph with n vertices, compute a minimum-capacity global cut (the smallest cut separating any two non-empty subsets of vertices) in polynomial time without computing all-pairs s-t maximum flows." I noted that running Dinic's s-t min-cut between a fixed source and all other n - 1 vertices requires n - 1 max-flow calls, which takes O(n * V^2 * E) = O(V^3 * E) time and has high implementation overhead. I proposed the Stoer-Wagner Algorithm. The interviewer challenged me: "Walk me through how maximum adjacency search contracts vertices, and prove why the cut-of-the-phase lemma guarantees finding the global minimum cut in O(V * E + V^2 log V) time." I explained that the algorithm operates in n - 1 phases without ever computing a single augmenting flow path. In each phase, we maintain an active set of vertices A, initialized with an arbitrary start vertex. We repeatedly append to A the unvisited vertex that has the maximum sum of edge weights to all current vertices in A (analogous to Prim's MST algorithm, tracked using a Fibonacci or indexed binary heap). Let s and t be the last two vertices added to A in this phase. The Cut-of-the-Phase Lemma mathematically proves that the cut separating {t} from V \ {t} is a minimum s-t cut in the current graph. We record the total edge weight incident to t as a candidate global min-cut, and then contract vertices s and t into a single merged vertex by summing their edge weights to all neighboring nodes. Repeating this contraction over n - 1 phases evaluates exactly n - 1 candidate cuts, of which the smallest is guaranteed to be the global minimum cut. He watched me write the adjacency priority updates, confirming strict O(V^2 log V + V * E) runtime and O(V^2) matrix space.