Google

The interviewer opened with an advanced topological and computational geometry challenge: "Given a polygon with n vertices that may be non-convex and self-intersecting, decompose its interior into the minimum number of pairwise non-overlapping monotone polygons in O(n log n) time so it can subsequently be triangulated in linear time." I explained that naively attempting to triangulate an arbitrary non-convex polygon with ears-clipping takes O(n^2), which degrades rapidly for n = 2 * 10^5. I proposed using a Plane Sweep-Line Algorithm to partition the polygon into y-monotone pieces. The interviewer followed up: "Identify the five distinct vertex classifications (start, end, split, merge, regular), and explain how 'helpers' associated with sweep-line edges eliminate split and merge vertices." I explained that vertices are categorized based on the relative y-coordinates of their adjacent incident edges and their interior angles: a split vertex has both neighbors lower with interior angle > 180 degrees, while a merge vertex has both neighbors higher with interior angle > 180 degrees. As a horizontal sweep-line moves downward, it maintains active polygon edges intersecting the sweep-line in a balanced binary search tree (BBST). For each active edge, we record a `helper` vertex—the lowest vertex traversed so far between this edge and its rightward neighbor. When the sweep encounters a split vertex v, it connects v via an interior diagonal to the helper of the edge immediately to its left in the BBST, instantly resolving the split. When encountering a merge vertex, its resolution is deferred: whenever the helper of its left-bounding edge is updated or an edge is removed, a diagonal is drawn back to the merge vertex if the old helper was itself a merge vertex. Connecting these diagonals removes all non-monotone indentations, decomposing the polygon into disjoint y-monotone sub-polygons in O(n log n) time and O(n) space. He then shifted to a probabilistic graph routing and distributed metric problem: "You are given a dense, weighted network of n nodes; construct a compact routing scheme that assigns every node an address of at most O(sqrt(n) * log n) bits and a local routing table of at most O(sqrt(n) * log n) entries, such that any node can route a packet to any destination with a stretch factor of at most 3 (the routed path length is at most 3 times the true shortest path distance)." I pointed out that storing full routing tables takes O(n) memory per node (O(n^2) total across the network), which exceeds local memory in distributed routing hardware. I proposed the Thorup-Zwick Compact Routing Scheme based on metric clustering and landmark selection. The interviewer cut in: "Walk me through how landmarks are sampled, define the cluster C(v) and the landmark bundle L(v), and show why the routed path achieves a stretch factor of at most 3." I broke down the two-level construction: we randomly sample a subset of nodes S of size O(sqrt(n) * log n) to act as landmarks. Every node v records its closest landmark p(v) in S and precomputes the shortest paths to all landmarks in its routing table (the landmark bundle L(v)). For non-landmark nodes, we define the cluster C(w) as the set of all nodes v that are strictly closer to w than to their own nearest landmark p(v): dist(v, w) < dist(v, p(v)). Each node w stores explicit routing table entries for every node in its cluster C(w). When node u routes a packet to destination v: if v is inside u's local cluster C(u), u routes directly to v along the true shortest path; if v is outside C(u), u forwards the packet toward v's nearest landmark p(v) (which is embedded into v's topological address). Once the packet reaches p(v), p(v) forwards it directly to v because v is guaranteed to belong to the cluster of p(v). By the triangle inequality, dist(u, p(v)) + dist(p(v), v) <= dist(u, v) + 2 * dist(v, p(v)) <= 3 * dist(u, v), guaranteeing a stretch factor of at most 3 with only O(sqrt(n) * log n) memory per node. For the final challenge, he introduced an algebraic matroid optimization on multi-graph edge partitions: "Given an undirected multigraph G with n vertices and m edges, find the maximum number of edge-disjoint spanning trees that can be packed into G, and construct the trees in polynomial time." I noted that repeatedly extracting Minimum Spanning Trees greedily fails because an early choice of a spanning tree can arbitrarily partition edges and prevent subsequent trees from completing (greedy packing violates the matroid intersection exchange condition). I reframed the task as Spanning Tree Packing using the Matroid Union of k Graphic Matroids via the Nash-Williams / Tutte Theorem. The interviewer challenged me: "Walk me through how the Matroid Union theorem determines the maximum packable trees, and how the augmenting path search transfers edges between candidate forests." I explained that a graph G contains k edge-disjoint spanning trees if and only if for every partition P of the vertex set V into |P| components, the number of cross-edges satisfies e(P) >= k * (|P| - 1). To construct the packing algorithmically, we treat each target spanning tree as an independent set in a graphic matroid M_1, M_2, ..., M_k. We maintain k disjoint forests F_1, F_2, ..., F_k. To insert an edge e that is currently unassigned: if there exists some forest F_i where F_i + e is acyclic, we immediately add e to F_i. If adding e creates a fundamental cycle in every forest, we construct an exchange graph: a directed edge exists from an edge e_in in F_i to an edge e_out not in F_i if removing e_out from F_j and inserting e_in into F_j keeps F_j cycle-free. We find a directed augmenting path from an available unassigned edge to an empty slot in any forest using BFS. Augmenting along the path shifts edges between forests, resolving fundamental cycles and expanding the total edge count of the k forests by 1. Repeating this augmentation packs the maximum number of edge-disjoint spanning trees in O(k^2 * n^2 * m) polynomial time and O(m) auxiliary space.