Google

The interviewer opened with an advanced algebraic graph recognition challenge: "Given an undirected graph G with n vertices and m edges, determine whether G is a Distance-Hereditary Graph (every connected induced subgraph preserves pairwise shortest-path distances) in strict linear O(n + m) time." I noted that verifying distance preservation naively requires running all-pairs shortest paths across all 2^n induced subgraphs, which is computationally intractable. I proposed recognizing distance-hereditary graphs via their structural characterization: a graph is distance-hereditary if and only if it admits a completely reducible decomposition into isolated vertices via a sequence of twin eliminations and pendant vertex removals (a Cograph / Rank-1 Modular Decomposition tree). The interviewer followed up: "Define true twins, false twins, and pendant vertices, and explain how Lexicographic BFS (Lex-BFS) or a bipartite elimination ordering certifies the decomposition in linear time." I explained that a pendant vertex has degree 1; false twins are vertices u and v with identical open neighborhoods N(u) = N(v); and true twins have identical closed neighborhoods N[u] = N[v]. Bandelt and Mulder proved that every distance-hereditary graph with at least two vertices contains at least one pair of twins or a pendant vertex. We run Lexicographic BFS with partition refinement to identify candidate twins and pendants: at each step, we locate a vertex v that is either pendant (degree 1) or has an identical neighborhood hash/list to an adjacent or non-adjacent sibling u. We contract or delete v, log the reduction step, and dynamically update the neighborhood partition classes of remaining adjacent nodes. If the graph reduces to a single vertex without encountering a house, hole (induced cycle of length >= 5), domino, or gem subgraph, the graph is distance-hereditary. Because partition refinement processes each edge a constant number of times, the entire test and decomposition tree construction completes in strict O(n + m) time and O(n + m) space. He then shifted to a computational geometry and kinetic data structures problem: "You are given n moving points on a 1D line, where each point's trajectory is an algebraic function of time x_i(t) = v_i * t + x_i(0); maintain the dynamic convex hull (upper and lower envelope of positions) and answer queries for the maximum coordinate at any continuous time t >= 0, processing certificate failures efficiently as velocities cause rank swaps." I pointed out that periodically re-sorting points at discrete time intervals (time-stepping) either misses critical collision events if the step size delta_t is too large, or wastes computation if delta_t is too small. I proposed a Kinetic Tournament Tree (KTT) or Kinetic Convex Hull maintained via Kinetic Data Structures (KDS). The interviewer cut in: "Walk me through how internal nodes maintain certificates of validity, and how the global event priority queue updates when a trajectory certificate fails." I explained that a Kinetic Data Structure maintains a combinatorial attribute (here, the upper envelope of linear functions) augmented with a set of boolean assertions called certificates that prove the current combinatorial state remains correct. In our tournament tree over linear trajectories, each internal node compares two candidate lines L_a(t) and L_b(t) and stores the line with the greater value; its associated certificate asserts that L_a(t) >= L_b(t). The certificate's expiration time is the future real root of L_a(t) - L_b(t) = 0 where t > t_current. We insert the expiration times of all internal node certificates into a global priority queue of discrete events. When the simulation clock advances to an event time t_event: the certificate of the failing node is invalidated because the two trajectories cross. We swap the winner pointer at that internal node, recompute the intersection times of its new winner against its parent and sibling, replace the outdated certificates in the priority queue, and resume. Basch, Guibas, and Hershberger proved that for linear trajectories, the upper envelope changes combinatorial structure at most O(n * alpha(n)) times (Davenport-Schinzel sequence of order 1). Thus, processing all structural changes across continuous time takes O(n * alpha(n) * log n) total time, answering online extreme queries in O(1) time at any instant. For the final challenge, he introduced an algebraic spectral and metric embedding problem: "Given an arbitrary finite metric space (X, d) on n points, construct a low-distortion metric embedding into a Euclidean space l_2 of dimension O(log^2 n) such that for all point pairs u, v in X, their Euclidean distance satisfies c * d(u, v) <= ||f(u) - f(v)||_2 <= d(u, v) with distortion at most O(log n), in polynomial time." I recognized this as Bourgain's Metric Embedding Theorem, a foundational result connecting combinatorial graph metrics to continuous Euclidean geometry. The interviewer challenged me: "Walk me through the randomized subset projection mechanics, explain how coordinates are scaled, and show why O(log^2 n) dimensions suffice to preserve distances with O(log n) distortion." I explained that the embedding constructs coordinates by measuring distances to randomly sampled subsets of varying granularities. We iterate through scales j from 1 to L = ceil(log_2 n). For each scale j, we randomly pick k = O(log n) independent subsets of X, denoted S_{j, 1}, S_{j, 2}, ..., S_{j, k}, where each subset is formed by including every point of X independently with probability p_j = 2^(-j). This produces a total of d = L * k = O(log^2 n) subsets. For any point u in X, its coordinate corresponding to subset S is defined as the point-to-set shortest distance: f_S(u) = min_{s in S} d(u, s). The complete coordinate vector f(u) in R^d is the concatenation of all d values, normalized by 1 / sqrt(d). For any two points u and v with metric distance d(u, v), the coordinate-wise difference |f_S(u) - f_S(v)| <= d(u, v) by the triangle inequality, which guarantees that ||f(u) - f(v)||_2 <= d(u, v) (no expansion). Conversely, by analyzing metric balls of radii r_j = 2^j around u and v, at each scale j there is a constant probability that a random set S contains a point near u while containing no points near v, yielding a coordinate separation of Omega(d(u, v) / log n). Summing these independent projections across the O(log^2 n) coordinates guarantees that ||f(u) - f(v)||_2 >= Omega(d(u, v) / log n) with high probability, achieving an optimal O(log n) distortion embedding in O(n^2 log^2 n) construction time and O(n log^2 n) memory.