Google

The interviewer opened with an advanced algebraic graph theory and lattice counting problem: "Given an undirected simple graph G with n vertices, compute its Chromatic Polynomial P_G(k)—the polynomial whose evaluation at integer k yields the exact number of proper k-colorings of G—in O(2^n * poly(n)) time without using deletion-contraction tree branching, which degrades to O(2.414^n) in the worst case." I pointed out that the classical deletion-contraction recurrence P_G(k) = P_{G \setminus e}(k) - P_{G / e}(k) explores an exponential recursion tree bounded only by the Fibonacci-like sum of spanning forests. I proposed using Inclusion-Exclusion over Independent Sets via Fast Walsh-Hadamard / Subset Convolution (Björklund-Husfeldt-Koivisto). The interviewer followed up: "Walk me through how the number of proper k-colorings expands via independent set covers, and how polynomial interpolation recovers all n coefficients of P_G(k) in O(n^2 * 2^n) time." I explained that a proper k-coloring partitions V into k non-empty independent sets. Let a(S) be an indicator equal to 1 if subset S is an independent set in G, and 0 otherwise. The number of ordered partitions of V into j non-empty independent sets is given by the j-th convolution power of a(S) evaluated at the full universe V: c_j = (a^{*j})(V). Computing standard subset convolution takes O(n^2 * 2^n) time by ranking subsets by size |S|, applying the Fast Zeta Transform (SOS DP), performing pointwise polynomial multiplication of rank vectors, and applying the Fast Möbius Inversion. The number of proper colorings using at most k colors is then given by the linear combination sum_{j=1}^n (k)_j * (c_j / j!), where (k)_j = k * (k - 1) * ... * (k - j + 1) is the falling factorial. Because P_G(k) is a polynomial in k of degree exactly n, we evaluate this sum at n + 1 distinct values of k in O(n^2 * 2^n) total time, then run Lagrange Polynomial Interpolation or Newton basis conversion in O(n^2) time to extract the exact integer coefficients of P_G(k) in O(n^2 * 2^n) time and O(2^n) space. He then shifted to a computational geometry and kinetic dynamic partition problem: "Given n stationary points in the 2D plane and a stream of online queries, each specifying an arbitrary directed line L, compute the 2D Centerpoint of the point set or find the Tukey Depth (Halfspace Depth) of a query point q in O(n log n) time, and verify whether a point with depth at least ceil(n / 3) always exists." I noted that testing all halfspaces for a candidate point takes O(n^3) naively, and finding the centerpoint is equivalent to finding a point that cannot be separated by any halfspace containing fewer than ceil(n / 3) points. I proposed using Circular Angular Sorting paired with Circular Two-Pointer Duality and Centerpoint Intersection via Helly's Theorem. The interviewer cut in: "Walk me through how radial line sweeping computes the exact Tukey depth of a point q in O(n log n) time, and how the centerpoint is constructively located via radon partitions or medians of linear projections." I broke down the two parts: First, to compute the Tukey depth of a fixed point q: we translate q to the origin (0, 0). For each of the n data points P_i, we compute its polar angle theta_i = atan2(y_i, x_i) in [0, 2*pi). We sort these angles in O(n log n) time. A directed halfspace passing through q is parameterized by an angle alpha; the number of points in the halfspace corresponds to the number of points whose polar angles fall in the circular interval [alpha, alpha + pi). As alpha sweeps through the sorted angles, points enter and leave this interval one by one. Maintaining the active count via two pointers evaluates the point count of all 2n combinatorial halfspaces passing through q in O(n) sweep time. The minimum count across the sweep is the exact Tukey depth of q. Second, to construct a centerpoint: by the Centerpoint Theorem (a consequence of Helly's Theorem on convex compact sets), every finite set of n points in R^2 admits a point with Tukey depth at least ceil(n / 3). We construct it in O(n) deterministic time using Jadhav and Mukhopadhyay's algorithm: we compute iterated Radon partitions by recursively grouping points into sets of 6, finding the intersection point of two triangles formed by Radon points, and pruning points outside the convex hull of projected medians, achieving the centerpoint in strict O(n) time and O(n) space. For the final challenge, he introduced an algebraic string structure and non-local periodicity problem: "Given an arbitrary string s of length n over an integer alphabet, find all maximal runs (maximal periodic subsegments of exponent at least 2) without building a full suffix array or Suffix Automaton, using the Main-Lorentz Divide-and-Conquer Algorithm with Four-Russians speedup in O(n log n) deterministic time." I pointed out that while Kolpakov-Kucherov finds runs in O(n) time via Lyndon trees, its implementation overhead is massive. The Main-Lorentz algorithm directly isolates periodic repetitions across divide-and-conquer boundaries using Longest Common Extensions (LCE). The interviewer challenged me: "Walk me through how splitting the string at midpoint m partitions repetitions into left-crossing and right-crossing squares, and how LCE queries over prefixes and suffixes identify the maximal periodic extension intervals in O(n / step) time." I explained that we split s[L...R] at its midpoint m = floor((L + R) / 2) and recursively find runs completely inside s[L...m] and s[m+1...R]. To detect runs crossing the boundary m: every such run of period p must contain a square u u of period p crossing m. A square of length 2p crossing m must intersect either the position m or m + 1. We iterate over all possible half-lengths p from 1 to (R - L + 1) / 2. For a fixed p, we place discrete anchor pins spaced p characters apart: pos_1 = m, pos_2 = m - p, pos_3 = m + p. Any square of period p that crosses m must cover at least one adjacent pair of pins. For each pinned offset pos: we define two LCE queries: L_1 = LCE_rev(s[0...pos], s[0...pos + p]) (the longest common suffix ending at pos and pos + p), and L_2 = LCE_fwd(s[pos + 1...n], s[pos + 1 + p...n]) (the longest common prefix starting at pos + 1 and pos + 1 + p). If L_1 + L_2 >= p, a periodic repetition of period p exists covering the anchor. The entire maximal run spans from pos - L_1 + 1 to pos + p + L_2. Precomputing a Sparse Table over the rolling hashes or an O(1) LCE structure allows each check to take O(1) time. Summing over all p from 1 to n/2 across the recursion gives sum_{levels} O(n/p) for anchors, yielding the recurrence T(n) = 2 * T(n/2) + O(n log n), which solves to O(n log^2 n), and by aligning pins strictly to multiples of p, simplifies to strict O(n log n) deterministic time and O(n) space.