Google

The interviewer opened with an advanced shortest-path sensitivity and fault-tolerant oracle challenge: "Given a directed graph G with n vertices, m non-negative edges, and a designated source s, construct a data structure that answers Single-Source Replacement Paths (SSRP) queries: given any edge e on the shortest path tree T_s, compute the length of the shortest path from s to every other vertex v in G \ {e} in sub-quadratic total time." I noted that deleting each tree edge one by one and re-running Dijkstra takes O(n * (m + n log n)), which approaches O(n^2 log n) or worse on dense graphs. I proposed the Demetrescu-Thorup / Bernstein-Karger Replacement Paths framework using Heavy-Light Decomposition over the shortest path tree paired with a specialized Segment Tree of Cross-Edges. The interviewer followed up: "Walk me through how non-tree edges bypass an edge failure on the shortest path, and how the tree interval is queried in logarithmic time per replacement." I explained that let P(s, v) be the unique s-to-v path in T_s. When an edge e = (u, w) on this path fails, any valid alternative s-to-v path must depart from T_s at an ancestor of u, traverse a non-tree cross-edge (x, y), and rejoin T_s at a descendant of w (or at v itself). The length of such a detour path is dist_G(s, x) + weight(x, y) + dist_{T_s}(y, v). Notice that the term dist_G(s, x) + weight(x, y) - dist_{T_s}(s, y) depends only on the cross-edge (x, y) and not on the specific failed edge e. For every non-tree edge (x, y), it provides an alternative bypass for every tree edge along the tree path from lca(x, y) to y. We can assign each non-tree edge a detour weight w'(x, y) = dist_G(s, x) + weight(x, y) - dist_T(s, y), and insert this value into a range minimum segment tree over the tree path intervals using Euler Tour or Heavy-Light Decomposition. Querying the replacement distance after deleting edge e reduces to querying the minimum detour value covering e in the segment tree and adding dist_{T_s}(s, v), answering queries in O(log n) time after an O(m log n) preprocessing phase. He then shifted to an online data structure scenario in computational topology and metric spaces: "Given an arbitrary metric space (X, d) on n points where the metric distance function is accessible only as a black-box oracle d(p, q), build a dynamic search index that supports approximate Nearest Neighbor Search (ANN) and Range Queries under arbitrary continuous metric distances in sub-linear time, without requiring Euclidean coordinates." I noted that spatial trees like KD-Trees, R-Trees, or Paraboloid Lifting break down completely in non-Euclidean or high-intrinsic-dimension spaces where coordinates do not exist. I proposed the Cover Tree data structure (Beygelzimer, Kakade, and Langford). The interviewer cut in: "Walk me through the three structural invariants of a Cover Tree (Nesting, Covering, and Separation), and explain how point insertion descends levels without backtracking." I broke down the invariants across discrete geometric levels i in Z, where each level has a scale radius 2^i: First, Nesting asserts that C_i is a subset of C_{i-1} (points at coarse levels persist down into finer levels). Second, Covering asserts that for every point p in C_{i-1}, there is a parent point q in C_i such that d(p, q) <= 2^i, meaning level i covers level i-1 with balls of radius 2^i. Third, Separation asserts that for any distinct pair p, q in C_i, d(p, q) > 2^i, ensuring that level i never clusters redundant points. To insert a point p, we start at the root at top level i_max and maintain a candidate set Q of nodes in C_i within distance 2^i of p. We expand Q to its children at level i-1 and prune any candidate whose distance to p exceeds the covering radius. The search descends until d(p, Q) <= 2^i is satisfied for some level, where p is inserted as a child. By the separation property, the number of candidates retained at each level is bounded by the doubling dimension c^O(1) of the metric space, guaranteeing O(c^6 * log n) time per query and insertion using strict O(n) space. For the final challenge, he introduced an algebraic spectral graph and tree-packing theorem on directed graphs: "Given a directed weighted graph G with n vertices and a designated root r, compute the exact minimum-weight directed spanning tree (arborescence) rooted at r in O(m log n) time, and prove why greedy cycles can be contracted without losing optimality." I identified this immediately as Edmonds' Branching Algorithm (Chu-Liu-Edmonds). I noted that standard Prim's or Kruskal's MST algorithms fail because directed cycles cannot simply be broken by dropping an arbitrary maximum edge. The interviewer challenged me: "Walk me through how Tarjan accelerated Chu-Liu-Edmonds using skew heaps and lazy weight offsets, and explain how contracted cycle potentials unpack to form the final arborescence." I explained that for every vertex v != r, we must select exactly one incoming edge to minimize total weight. We greedily pick the minimum-weight incoming directed edge for each node. If this selected edge set forms no cycles, it is already the optimal arborescence. If one or more directed cycles C are formed, we must break each cycle by replacing one of its incoming edges with an external incoming edge. Tarjan maintained the candidate incoming edges for each component inside a mergeable heap (like a Skew Heap or Randomized Meldable Heap). When a directed cycle C is detected via path compression (DSU), we contract all vertices in C into a single super-vertex. Crucially, when an external edge e = (u, v) entering node v in C is considered, adopting e requires dropping the internal cycle edge in_edge(v) that currently enters v; therefore, its effective marginal cost is w'(e) = w(e) - w(in_edge(v)). We apply this weight adjustment lazily to the entire heap of incoming edges of v by setting a lazy tag on the heap root before merging the heaps of all nodes in C. Repeating this contraction on newly formed cycles reduces the graph to the root r. We then traverse the contracted components in reverse topological order: for each contracted super-vertex, we unpack its internal cycle and remove the single edge that collided with the chosen incoming edge. Using skew heaps with lazy tags, the entire contraction and expansion runs in strict O(m log n) time and O(n + m) space.