Google

The interviewer opened with an advanced combinatorial routing challenge on directed planar graphs: "Given a directed planar graph G embedded in the plane with non-negative edge weights, and k pairs of source-sink terminals (s_1, t_1), ..., (s_k, t_k) all lying on the boundary of the infinite outer face, find k pairwise edge-disjoint directed paths connecting each s_i to t_i in polynomial time, or certify that no such paths exist." I noted that for general directed graphs, edge-disjoint paths are NP-complete even for k = 2. However, when terminals reside on a single face of a planar embedding, the problem simplifies via topological homological invariants. I proposed Schrijver's Directed Planar Routing via Cohomology and Circulations (or the Frank-Robertson-Seymour Planar Disjoint Paths framework). The interviewer followed up: "If paths cross, their topological intersection number is non-zero; explain how mapping path demands to a dual homology group transforms edge-disjoint routing into a minimum-cost circulation or planar cut problem." I explained that we draw virtual demand curves in the outer face connecting each t_i back to s_i, closing each desired path into a cycle. The system of k paths is routable if and only if these closed cycles can be realized without exceeding edge capacities and without creating unavoidable cross-intersections (topological braiding). We translate this into a dual flow problem: in the planar dual graph G*, directed dual cycles correspond to cuts in the primal graph. For any simple dual cycle C*, the net homological flux of the demand curves crossing C* must not exceed the capacity of the primal edges intersected by C*. By the Okamura-Seymour / Frank theorem, the absence of an overloaded cut is both necessary and sufficient. We compute the dual shortest paths across faces using Dijkstra on the planar dual to find the bottleneck cut. If all cut conditions hold, the paths are extracted by computing a circulation on the primal graph that pushes unit flows along non-crossing facial paths, peeling off each s_i-to-t_i path in O(k * n log n) time. He then shifted to an advanced computational geometry and parametric optimization scenario: "Given n points in the 2D plane, find a line L that minimizes the maximum Euclidean distance from any point to L (the Minimum Width Annulus / Linear Chebychev Approximation), in strictly sub-quadratic time without approximating the angle." I pointed out that iterating over all pairs of points to define line slopes takes O(n^2), which is too slow when n reaches 10^5. I proposed using Megiddo's Prune-and-Search technique paired with Upper/Lower Envelope Intersection over Dual Line Arrangements. The interviewer cut in: "Walk me through how the dual transformation maps the Chebyshev line search into finding the narrowest vertical strip between two convex envelopes, and explain how Megiddo's prune-and-search discards a constant fraction of points in linear time." I broke down the duality: a candidate line L: y = a * x + b has vertical distance to a point P_i = (x_i, y_i) equal to |y_i - (a * x_i + b)|. The optimal line L must minimize max_i |y_i - a * x_i - b| / sqrt(1 + a^2). For a fixed slope a, the optimal intercept b is precisely the midpoint between the upper envelope U(a) = max_i (y_i - a * x_i) and the lower envelope D(a) = min_i (y_i - a * x_i), and the vertical strip width is W(a) = U(a) - D(a). In the dual plane, each point P_i becomes a line P_i*: y = -x_i * a + y_i. U(a) is the upper convex envelope of these dual lines, and D(a) is the lower convex envelope; W(a) is a convex unimodal function of a. To find the optimal slope a* in linear time without constructing the full O(n^2) arrangement, we pair up the dual lines randomly to form n/2 line intersections. We find the median x-coordinate (slope) a_med of these intersection points in O(n) time via quickselect. We evaluate the subgradient of W(a) at a_med in O(n) time by finding the extreme primal points. Depending on whether a* lies to the left or right of a_med, at least half of the intersection points lie on the inactive side. For each pair whose intersection lies on the inactive side, one of the two lines is guaranteed not to define the envelope on the side containing a*. We discard that redundant line, pruning at least n/4 lines in O(n) time. The recurrence T(n) = T(3n/4) + O(n) solves to strict O(n) deterministic time and O(n) space. For the final challenge, he introduced an algebraic combinatorics and polynomial interpolation problem: "Given an integer n, compute the exact number of unlabeled non-isomorphic graphs on n vertices in O(2^n * poly(n)) time using the Polya Enumeration Theorem and cycle index polynomials, without generating any graphs explicitly." I noted that the number of graphs grows as 2^(n(n-1)/2) / n!, meaning exhaustive isomorphism testing is completely intractable even for n = 20. I proposed evaluating the Cycle Index Polynomial of the Edge Permutation Group induced by the Symmetric Group S_n acting on vertex pairs. The interviewer challenged me: "Walk me through how an integer partition of n induces a specific cycle structure on the n*(n-1)/2 unordered pairs of edges, and show how evaluating the polynomial at (2, 2, ..., 2) yields the exact unlabeled graph count." I explained that two graphs are isomorphic if they belong to the same orbit under the action of the symmetric group S_n on the set of (n choose 2) possible edges. By Burnside's Lemma and Pólya's Enumeration Theorem, the number of non-isomorphic graphs is (1 / n!) * sum_{g in S_n} 2^{c(g)}, where c(g) is the number of disjoint cycles in the permutation of *edges* induced by the vertex permutation g. Permutations with the identical cycle type on vertices have identical induced cycle structures on edges. Any cycle type of S_n corresponds to an integer partition of n: lambda = (1^{k_1}, 2^{k_2}, ..., n^{k_n}), where k_i is the number of cycles of length i. The number of permutations in S_n having cycle type lambda is n! / prod_{i=1}^n (i^{k_i} * k_i!). For a given partition lambda, the number of induced edge cycles c(g) is computed using closed-form cycle arithmetic: (1) each vertex cycle of odd length L induces (L - 1) / 2 edge cycles of length L; (2) each vertex cycle of even length L induces (L - 2) / 2 edge cycles of length L and 1 edge cycle of length L / 2; (3) every pair of distinct vertex cycles of lengths L_1 and L_2 induces gcd(L_1, L_2) edge cycles of length lcm(L_1, L_2). Because the number of integer partitions of n is p(n) (for n = 60, p(60) = 966,467, well within O(poly(n))), we iterate through all partitions of n, compute c(g) in O(n^2) arithmetic steps per partition, evaluate 2^{c(g)}, and sum them up with their group conjugacy class sizes. This computes the exact count in O(p(n) * n^2) time and O(n) space.