Google

The interviewer opened with an advanced algebraic graph theory and lattice geometry challenge: "Given an undirected simple graph G with n vertices and m edges, determine its Treewidth tw(G) and construct an exact optimal Tree Decomposition in O(2^n * n^3) time without relying on Bodlaender's algorithm, whose astronomical constant factor (exceeding 2^{tw^3}) renders it completely impractical for actual execution." I noted that computing treewidth is NP-hard, and while Bodlaender’s linear-time FPT algorithm proves polynomial computability for fixed k, its tower-of-exponentials constant is unusable. I proposed utilizing Bouchitté-Todinca's Minimal Separators and Potential Maximal Cliques (PMCs) framework combined with dynamic programming over connected vertex subsets. The interviewer followed up: "Walk me through what defines a Potential Maximal Clique, how minimal separators partition G \ S into full components, and how subset dynamic programming identifies the optimal chordal completion." I explained that treewidth is the minimum clique number minus 1 over all chordal completions (triangulations) of G. A vertex subset Omega is a Potential Maximal Clique if it forms a maximal clique in some minimal triangulation of G. By Bouchitté and Todinca's characterization, Omega is a PMC if and only if: (1) G \ Omega has no full component (a connected component whose neighborhood in G is all of Omega), and (2) for every pair of vertices u, v in Omega, either (u, v) is an edge or there exists a connected component C in G \ Omega such that both u and v are neighbors of C. We enumerate all minimal separators of G in O(n^3 * |Delta|) time using a search over neighborhoods of connected components. From the minimal separators, we list all PMCs in O(n^2 * |Delta|^2) time. For each connected induced subgraph or full component block (S, C) where S is a minimal separator and C is a component of G \ S, we define DP[S, C] as the minimum treewidth of triangulating C cup S such that S remains a clique. For a valid PMC Omega containing S and contained in S cup C, Omega breaks C \ Omega into smaller sub-components C_1, C_2, ..., C_r. The recurrence is given by DP[S, C] = min_{Omega} max(|Omega| - 1, max_i DP[N(C_i), C_i]). Memoizing over the O(2^n) induced subgraphs computes the exact treewidth and extracts the optimal tree decomposition in strict O(2^n * n^3) time and O(2^n) space. He then shifted to a computational geometry and kinetic dynamic partition problem: "Given n line segments in the 2D plane forming arbitrary polygonal obstacles and a point robot with a fixed polygonal footprint (a convex k-gon P), preprocess the scene to compute the exact Configuration Space Obstacle (C-space) boundary in O(k * n log(k * n)) time, and query whether a translated placement of P at position (x, y) collides with any obstacle in O(log(k * n)) time without using polygon-polygon clipping." I pointed out that checking intersection between a translated polygon P + t and each obstacle segment naively takes O(k * n) per position query, which is too slow for real-time motion planning. I proposed computing the Minkowski Sum (or Minkowski Difference) of each obstacle segment S_i with the reflected robot polygon -P, followed by constructing the Planar Map of the union of these Minkowski sums. The interviewer cut in: "The Minkowski sum of a line segment and a convex k-gon is a convex (k + 2)-gon; walk me through how merging their circular Gaussian diagrams constructs this in O(k) time, and how the Davenport-Schinzel bound prevents the combinatorial complexity of the union from exploding into O(k^2 * n^2)." I explained that for each obstacle segment S_i and the reflected convex polygon -P, their Minkowski sum C_i = S_i \oplus (-P) is geometrically convex and has at most k + 2 vertices. Because both S_i and -P are convex, their Minkowski sum is computed in O(k) time by merging their outer normal vectors (Gaussian maps) in angular sorted order around the unit circle, like merging two sorted arrays. The free configuration space of the robot's reference point is R^2 \setminus \bigcup_{i=1}^n C_i. The crucial structural property is that any two such Minkowski sum polygons C_i and C_j are pseudodiscs: their boundaries intersect at most twice. By Kedem, Livne, Pach, and Sharir's theorem, the boundary of the union of n pseudodiscs with at most k vertices each has combinatorial complexity bounded strictly by O(k * n * alpha(n)) (Davenport-Schinzel sequence of order 3), avoiding quadratic explosion. We construct this union using a divide-and-conquer sweep-line algorithm in O(k * n log^2(k * n)) time. We then build a Kirkpatrick or trapezoidal point-location DAG over the planar subdivision in O(k * n log(k * n)) time. When a query position (x, y) arrives, point location tests whether (x, y) falls inside an obstacle face in strict O(log(k * n)) time and O(k * n * alpha(n)) space. For the final challenge, he introduced an algebraic combinatorics and compressed sequence structure scenario: "Given an arbitrary string s of length n, build an index that supports Substring Rank Queries: given an arbitrary query substring w = s[i...j] and a character c, count the exact number of times character c appears immediately after an occurrence of w in s in O(1) time, consuming at most n * log_2(|Sigma|) + o(n log |Sigma|) bits of space." I noted that using a Suffix Tree or Suffix Automaton to find the locus of w and scanning its outgoing edges takes O(|w|) to locate and O(|Sigma|) to aggregate, which exceeds the O(1) query bound and consumes O(n log n) machine words (64n bits). I proposed utilizing the Compact Directed Acyclic Word Graph (CDAWG) combined with a Succinct Wavelet Tree over the CDAWG Edge Labels and Rank-Directory Arrays. The interviewer challenged me: "The CDAWG collapses both right-equivalent and left-equivalent states, bounding the number of vertices to at most 2 * e(s) where e(s) is the number of right-equivalence classes; walk me through how the CDAWG transition function encodes following characters, and how secondary succinct rank structures resolve the count in O(1) steps." I broke down the two-level structural representation: the CDAWG of string s is obtained by minimizing the Suffix Tree by merging isomorphic subtrees, which is equivalent to compressing the chains of degree-1 nodes in the Suffix Automaton. Blumer et al. proved that for any string s of length n, the CDAWG has at most 2 * e(s) <= 2 * r nodes and 3 * r edges, where r is the number of runs of identical characters in the Burrows-Wheeler Transform of s. Each state q in the CDAWG corresponds to a maximal equivalence class of substrings that share identical sets of left-contexts and right-contexts. For a node q, let its outgoing transition edges be labeled with characters a_1, a_2, ..., a_d. The count of times character c appears immediately after any substring in the equivalence class of q is simply the size of the right-context set (end-position set) of the target node reached by following edge c from q. To answer this in O(1) time: we index the end-position sizes |endpos(target(q, c))| directly. If the query substring w is represented by its locus (node q, offset k along edge e = (q, q')), then: (1) if offset k < length(e), the character following w is unique and deterministically fixed to e[k], so the count is identically |endpos(q')| for that specific character and 0 for all other characters; (2) if k == length(e), the query matches exactly at node q', and the count of following character c is non-zero if and only if q' has an outgoing edge labeled with c, whose value is |endpos(target(q', c))|. Storing these scalar sizes in an Elias-Fano compressed array and indexing the node transitions using succinct Elias-Fano predecessor bitvectors enables evaluating the exact frequency in O(1) time using n * log_2(|Sigma|) + o(n log |Sigma|) bits of total space.