Google

The interviewer opened with an advanced algebraic graph theory and polyhedral geometry problem on metric trees: "Given an n x n non-negative symmetric distance matrix D with D[i][i] = 0, determine whether D is an additive metric (can be realized as the pairwise shortest path distances in an edge-weighted tree T where the n elements are tree leaves with positive edge weights), and if so, reconstruct T with all internal nodes and edge weights in strict O(n^2) deterministic time." I noted that verifying triangle inequalities is insufficient because metric spaces in general do not embed into trees. I proposed using the Four-Point Condition paired with the Buneman-Saitou Neighbor-Joining or Buneman's Split Decomposition. The interviewer followed up: "Walk me through the exact algebraic form of the Four-Point Condition, and explain how the Gromov Hyperbolicity delta = 0 invariant detects tree metrics and extracts path lengths without searching an exponential tree space." I explained that a finite metric space (X, D) embeds isometrically into a tree if and only if for every four points x, y, z, w, the maximum two of the three sums D[x, y] + D[z, w], D[x, z] + D[y, w], and D[x, w] + D[y, z] are strictly equal (meaning the metric is 0-hyperbolic). To reconstruct T in O(n^2) time without testing all O(n^4) quartets, we build T incrementally: start with two leaves 1 and 2 connected by an edge of length D[1, 2]. When adding leaf k (from 3 to n), we pick any two already placed leaves i and j. The distance from k to the path between i and j, as well as the position of the projection point p where k branches off, is determined by the Gromov product (overlap function): (i . j)_k = (D[i, k] + D[j, k] - D[i, j]) / 2. This isolates the exact length of the new pendant edge to k and the distance from p to i. By traversing down the established tree branches using these projections and inserting new internal Steiner vertices where paths branch, each new leaf is placed in O(n) amortized steps. Verifying that the reconstructed tree preserves all entries of D takes O(n^2) time via tree traversals, certifying the additive tree metric in optimal O(n^2) time and O(n) space. He then shifted to a computational geometry and kinetic visibility problem: "Given an arbitrary simple polygon P with n vertices and an interior moving guard following an algebraic trajectory gamma(t) in P, determine whether P is Star-Shaped (has a non-empty visibility Kernel—the locus of all points from which the entire interior of P is visible), and maintain the dynamic Kernel as polygon edges are interactively translated in O(log n) time per update." I pointed out that testing whether a polygon is star-shaped is equivalent to finding the intersection of n interior half-planes defined by the directed boundary edges of P. While general half-plane intersection takes O(n log n), the angular ordering of polygon edges around the perimeter allows an optimal O(n) construction. I proposed Lee-Preparata's Kernel Construction Algorithm backed by a Dynamic Dual Convex Hull. The interviewer cut in: "Walk me through how the half-planes corresponding to reflex vertices bound the kernel, and how dynamic point-line duality maintains the intersection when edges undergo translation." I broke down the reduction: for each directed edge e_i = (v_i, v_{i+1}) of P, we define its inward-supporting half-plane H_i. The kernel K(P) is the convex polygon formed by the intersection of all n half-planes: K(P) = \bigcap_{i=1}^n H_i. In Lee-Preparata's algorithm, we observe that convex vertices do not constrain the kernel beyond their incident edges; the active constraints come strictly from the edges incident to reflex vertices. By sweeping around the perimeter, we maintain the active intersection using a double-ended queue (deque): when an incoming directed edge cuts across the currently accumulated half-plane polygon, vertices outside the edge's positive side are popped from the deque in O(1) amortized steps, constructing the kernel in O(n) time. To maintain the kernel under edge translations, we dualize each half-plane H_i: a_i * x + b_i * y + c_i >= 0 into a dual point or half-space in 3D projective space. The intersection of half-planes maps to the Upper Convex Hull of the dual points. Maintaining the dynamic kernel under translations reduces to maintaining a dynamic 2D/3D convex hull via an Overmars-van Leeuwen tree, answering point queries inside the kernel in O(log n) time and supporting edge updates in O(log^2 n) time. For the final challenge, he introduced an algebraic combinatorics and data structure scenario on compressed binary vectors: "Given an arbitrary static binary string B of length n containing m ones, build a Succinct Dictionary that supports rank_1(i) (count ones in B[0...i]) and select_1(k) (find the position of the k-th one) in strict O(1) worst-case time, while consuming only m * log_2(n / m) + O(m) + o(n) bits of space (matching the zeroth-order empirical entropy H_0(B) within redundancy bounds)." I noted that standard Jacobson or Clark-Munro bitvectors achieve O(1) rank/select, but their base storage is n + o(n) bits, which wastes memory on ultra-sparse vectors where m << n (e.g., m = 10^4 and n = 10^9). I proposed the Raman-Raman-Rao (RRR) Succinct Compressed Bitvector or Elias-Fano Quasi-Succinct Indexing. The interviewer challenged me: "Walk me through how the RRR structure partitions the bitvector into fixed blocks of length u, and how separating each block into a class c (Hamming weight) and offset o achieves the information-theoretic entropy bound while allowing O(1) rank queries via small universal tables." I broke down the two-tier combinatorial encoding: we partition B into micro-blocks of fixed bit-length u = floor((log_2 n) / 2). Each micro-block b of length u has some Hamming weight c = popcount(b) in {0, 1, ..., u}. Given weight c, there are exactly (u choose c) possible binary blocks. We represent b as an ordered pair (c, o), where c is the class identifier (requiring ceil(log_2(u + 1)) bits) and o is the lexicographical rank (offset) of b among all strings of length u with weight c (requiring ceil(log_2(u choose c)) bits). By Stirling's approximation and Jensen's inequality, summing ceil(log_2(u choose c)) over all blocks achieves strictly n * H_0(B) + O(n log log n / log n) bits, compressing the sequence to its zeroth-order entropy. To support O(1) rank queries without decompression, we build a two-level prefix-sum directory over macro-blocks of size U = u^2: macro-blocks store explicit 64-bit absolute counts every U bits, and intermediate micro-blocks store relative offsets. To query within a micro-block, we build a universal lookup table indexed by the pair (c, o) and a relative bit-position: Table[c][o][pos] returns the local rank within the block in O(1) time without accessing the raw bits. Because u = O(log n), the total size of this universal table is at most 2^u * u * log u = O(sqrt(n) * poly(log n)) bits, which is sub-linear o(n), resolving rank and select in O(1) worst-case time and optimal succinct space.