Google

The interviewer opened with an advanced graph-theoretic and algebraic matrix decomposition challenge: "Given a general undirected graph G with n vertices, construct a Gomory-Hu Cut Tree—a weighted tree on the same n vertices where the weight of the unique path bottleneck between any two vertices u and v equals their exact global s-t minimum cut capacity in G—in sub-cubic time without running n*(n-1)/2 independent max-flow computations." I noted that running Dinic's min-cut between all pairs of nodes takes O(V^2 * Flow(V, E)) = O(V^4 * E), which is completely intractable when n exceeds 1000. I proposed Gomory and Hu's recursive contraction algorithm, which requires exactly n - 1 max-flow calls. The interviewer followed up: "Walk me through how a single s-t cut splits the current equivalence block into two sub-problems, and explain why contracting external connected components preserves cut capacities across recursive steps without skewing subsequent cuts." I explained that the algorithm maintains a tree of vertex partitions, starting with a single node containing all vertices V. At any recursive step, we pick an arbitrary partition block containing at least two vertices, select two distinct vertices s and t within this block, and compute a minimum s-t cut (S, T) in a condensed auxiliary graph. Crucially, to prevent flow-path explosion, all vertices outside this block that fall on the S-side of earlier cuts are contracted into a single super-node, and all vertices on the T-side are contracted into another super-node. By submodularity of graph cuts (the uncrossing lemma), this contraction preserves the minimum cut value between any two vertices remaining in the active block. We insert an edge between s and t with capacity equal to this cut, split the active block into S \cap Block and T \cap Block, and reattach existing tree edges to s or t depending on which side of the cut their endpoints lie. Repeating this across n - 1 steps constructs the full Gomory-Hu tree in O(n * Flow(V, E)) time and O(V + E) space. He then shifted to a computational geometry and kinetic partitioning challenge: "Given n stationary points in a 2D plane and a query line L(t): a * x + b * y + c = 0, count the exact number of points lying on the positive side of L in O(1) query time after an O(n^2) preprocessing phase, without using approximate grid projections." I observed that standard 2D range trees or half-plane range reporting structures take O(log^2 n) or O(sqrt(n)) per query, which is too slow for an O(1) query guarantee. I proposed constructing the Dual Line Arrangement of the points and maintaining its Topological Sweep or Levels via a Directed Acyclic Subgraph (Zone Theorem / Dual Point-Line Duality). The interviewer cut in: "Walk me through the point-line dual transform (p_x, p_y) <-> y = p_x * x - p_y, and show how counting points above a primal query line translates to locating a point within the faces of the dual arrangement." I broke down the duality mapping: a point P = (p_x, p_y) maps to the dual line P*: y = p_x * x - p_y, and a primal query line L: y = m * x + k maps to the dual point L* = (m, -k). The primal condition that point P lies above line L (p_y > m * p_x + k) rearranges algebraically to m * p_x - p_y < -k, which is strictly equivalent to stating that the dual line P* passes below the dual point L*. Thus, counting the number of points above the primal line L is mathematically identical to counting how many dual lines pass below the dual point L* (the level of the point L* in the arrangement). The n dual lines partition the dual plane into an arrangement of O(n^2) convex faces. By precomputing the arrangement and its vertical ray-shooting or planar point-location trapezoidal map in O(n^2) time via topological sweep, each face stores the exact count of lines lying strictly below it. When a query line L arrives, we map it to point L*, locate its containing face in O(log n) time, and read the precomputed count—or by pre-binning slopes along the dual envelope, answer in O(1) amortized time using O(n^2) space. For the final challenge, he introduced an algebraic string and combinatorics on compressed words scenario: "Given a string s of length n generated by a Straight-Line Program (SLP)—a context-free grammar with m production rules where each non-terminal derives either a single character or the concatenation of two previous non-terminals—determine whether s contains a given pattern p of length k as a contiguous substring in O(m * k^2) time, without decompressing the potentially exponentially long string s." I pointed out that an SLP of size m can generate a string of length up to 2^m (e.g., Fibonacci strings), so decompressing s takes exponential Omega(2^m) time and memory, which crashes for m = 80. I proposed Karpinski-Rytter's Compressed Pattern Matching Algorithm via Boundary Substring Signatures. The interviewer challenged me: "Walk me through how a non-terminal rule X -> Y Z splits the occurrence of pattern p into prefix-suffix boundary matches, and what state invariants prevent redundant internal scans." I explained that for each production rule X -> Y Z, any occurrence of p in the string expanded by X either lies entirely within the string expanded by Y, entirely within the string expanded by Z, or crosses the boundary between Y and Z. The first two cases are resolved inductively by recording a boolean reachability flag `contains(X, p)`. For the boundary-crossing case, the pattern p of length k must be split into a non-empty prefix of length d and a non-empty suffix of length k - d, such that the prefix matches a suffix of Y's expansion and the suffix matches a prefix of Z's expansion. Because p has length k, we only need to preserve a prefix of length min(|X|, k - 1) and a suffix of length min(|X|, k - 1) for every non-terminal X. We evaluate these k-bounded boundary signatures for each rule from bottom to top using the KMP failure function or Aho-Corasick automaton over p in O(k) time per rule. An occurrence is confirmed if either sub-rule already contains p, or if for some split position 1 <= d < k, the suffix of length d of Y matches p[0...d-1] and the prefix of length k - d of Z matches p[d...k-1]. Propagating this bottom-up across all m production rules verifies the presence of p in O(m * k^2) (or O(m * k) with fast prefix-suffix hashing) time and O(m * k) space.