Google

The interviewer opened with an advanced shortest-path query problem on dynamic planar graphs: "Design an exact Distance Oracle for an undirected planar graph G with n vertices and non-negative edge weights that can be constructed in O(n log n) preprocessing time, uses O(n) space, and answers point-to-point shortest-path queries between any two arbitrary vertices in O(n^(1/2)) time." I noted that naive all-pairs shortest paths uses O(n^2) space, which is impossible when n reaches 10^5, while standard Dijkstra takes O(n log n) per query. I proposed building a Frederickson Topology Tree / Klein-Mozes Distance Oracle based on recursive planar graph division via Cycle Separators. The interviewer followed up: "Walk me through how r-divisions partition a planar graph into boundary vertices, and how the Monge property of boundary-to-boundary distance matrices allows searching without relaxing all interior edges." I explained that an r-division partitions the n-vertex planar graph into O(n / r) edge-disjoint regions, each containing at most r vertices and O(sqrt(r)) boundary vertices lying on a constant number of cyclic faces. For each region, we precompute all-pairs shortest paths among its boundary vertices. Crucially, because boundary vertices lie along cyclic faces of planar embeddings, the boundary-to-boundary distance matrix satisfies the Monge property: dist(a, c) + dist(b, d) <= dist(a, d) + dist(b, c) for cyclical indices a < b < c < d. When a query between arbitrary vertices u and v arrives, we locate the regions containing u and v, compute their distances to their respective region boundaries, and then resolve the boundary-to-boundary transit using the SMAWK algorithm or recursive divide-and-conquer on Monge matrices. By setting r = n, the oracle achieves O(n) total space and answers shortest-path queries in O(sqrt(n)) time. He then shifted to a computational geometry and discrete-point optimization problem: "Given n points in a 2D plane and a set of m query disks, each specified by a center C and radius R, find the maximum weight of any point lying strictly inside each disk in O(log^2 n) query time." I pointed out that 2D range trees only work for axis-aligned bounding boxes, while brute-forcing all points for each disk takes O(m * n). I proposed lifting the 2D points onto a 3D Paraboloid followed by 3D Half-Space Range Reporting. The interviewer cut in: "Walk me through the exact algebraic lifting transformation (x, y) -> (x, y, x^2 + y^2), and show how testing whether a point is inside a circle becomes a planar half-space test in 3D." I broke down the algebraic reduction: the condition for a 2D point P = (x, y) to lie inside a circle with center (a, b) and radius R is (x - a)^2 + (y - b)^2 <= R^2. Expanding this yields x^2 - 2ax + a^2 + y^2 - 2by + b^2 <= R^2, which rearranges to (x^2 + y^2) - 2ax - 2by + (a^2 + b^2 - R^2) <= 0. By mapping every 2D point (x, y) to a 3D point (x, y, z) where z = x^2 + y^2, the test simplifies to z - 2ax - 2by + (a^2 + b^2 - R^2) <= 0. This is the equation of a 3D linear half-space bounded by the plane z = 2ax + 2by - (a^2 + b^2 - R^2). Thus, the problem of querying points inside a 2D circular disk reduces to querying 3D points lying below a query plane. By building a 3D Convex Hull or a 3D Half-Space Range Tree over the lifted points, we evaluate maximum-weight interior points using fractional cascading in O(log^2 n) time per query and O(n log n) preprocessing space. For the final challenge, he introduced an algebraic string structure and minimal suffix grammar problem: "Given a string s of length n, construct the Compact Directed Acyclic Word Graph (CDAWG) in linear time, and explain why its state space is bounded by 2e where e is the number of distinct right-extensions, making it strictly smaller than both the Suffix Tree and the Suffix Automaton." I pointed out that while a Suffix Automaton (SAM) has up to 2n - 1 states and a Suffix Tree has up to 2n leaves and internal nodes, the CDAWG combines the structural minimization of DAWGs with the edge-compression of Suffix Trees. The interviewer challenged me: "Walk me through how the equivalence relation of the CDAWG contracts non-branching states in the Suffix Automaton, and how Ukkonen-style edge labels are maintained." I explained that in a standard Suffix Automaton, states represent equivalence classes of substrings sharing the exact same set of end-positions (endpos). However, many states in a SAM have out-degree exactly equal to 1, representing non-branching deterministic paths. The CDAWG contracts all non-branching chains of states in the SAM into single compressed edges labeled with substring intervals [L, R], exactly mirroring how a Suffix Tree compresses non-branching paths of a Trie. The states of the CDAWG correspond only to the essential equivalence classes that possess at least two distinct character extensions or represent suffix endpoints. By applying Blumer's or Inenaga's online construction algorithm, transitions are inserted in O(n) total time. Because the CDAWG eliminates all degree-1 states, the number of states is bounded by min(n, 2 * e_max), achieving the absolute minimal automaton representation of all substrings of s in O(n) time and O(n * alphabet) memory.