Google

The interviewer opened with an online algorithmic game theory and dynamic matching challenge on two-sided markets: "Given an arbitrary bipartite graph G = (L, R, E) where the offline side L with n vertices is known in advance, and the online side R with m vertices arrives one by one in random order (the Prophet Inequality / Random Order Model), design an online edge-selection strategy that achieves a strictly greater than (1 - 1/e) competitive ratio against the offline maximum matching, running in O(1) decision time per arriving vertex." I pointed out that under adversarial arrival order, the Karp-Vazirani-Vazirani (KVV) RANKING algorithm achieves 1 - 1/e ≈ 0.632, which is the tight upper bound for worst-case adversaries. However, under the Random Arrival Model (ROM), Mahdian and Yan, as well as Karande, Mehta, and Tripathi, broke the 1 - 1/e barrier. I proposed using the Perturbed Water-Filling / Random Order Ranking Algorithm. The interviewer followed up: "Walk me through how randomized rank assignments break the 1 - 1/e barrier under uniform random arrival permutations, and how the vertex potential function certifies an approximation ratio of at least 0.696 or 0.727." I explained that at preprocessing time, each offline vertex u in L draws an independent rank Y_u uniformly at random from [0, 1]. When an online vertex v in R arrives along with its incident edges, it inspects all currently unmatched neighbors u in L and selects the neighbor that maximizes a monotone decreasing trade-off function g(Y_u) = 1 - exp(Y_u - 1). Because the arrival permutation of R is drawn uniformly at random from S_m, the correlation between an offline vertex's availability and its rank is smoothed across time. By setting up a continuous differential factor-revealing LP over the time interval t in [0, 1] (where t represents the fractional progression of arriving vertices), the probability that an offline vertex u of rank y is matched by time t satisfies a system of delay-differential equations. Analyzing the dual potential of the edge-allocation LP proves that the marginal probability of matching an edge strictly dominates the adversarial boundary, elevating the competitive ratio to at least 0.696 in O(deg(v)) time per arrival and O(n + m) space. He then shifted to a computational geometry and topological persistence scenario in spatial data: "Given a finite point cloud P of n points in R^3 and a filtration parameter epsilon > 0, construct the 1-skeleton of the Vietoris-Rips Complex VR(P, epsilon) and compute its Persistent Homology barcode for 1-dimensional topological loops (H_1 persistence intervals) in O(m^omega) or sub-cubic time, where m is the number of simplices, without constructing empty high-dimensional cliques." I noted that persistent homology tracks topological features (connected components H_0, loops H_1, voids H_2) as spatial complexes expand. Naive boundary matrix reduction on the complete simplex filtration up to dimension 2 takes O(m^3) operations. I proposed using the Ripser / Twist Algorithm with Discrete Morse Reductions and Apparent Pair Pruning. The interviewer cut in: "Walk me through how the boundary matrix d_2 represents triangle boundaries, explain how column-addition reduction extracts (birth, death) pairs, and show why pairing apparent persistence intervals skips matrix columns entirely." I broke down the algebraic pipeline: the boundary matrix D_k maps k-simplices to (k - 1)-simplices over the field Z_2. For H_1 features, we care about the boundary operator d_2: C_2 -> C_1, where columns represent 2-simplices (triangles) and rows represent 1-simplices (edges), sorted by their filtration entrance times (length of longest constituent edge). A standard reduction reduces D from left to right using column additions: if column j has low(j) = i (the lowest non-zero row index), and an earlier column k < j has low(k) = i, we set col(j) = col(j) + col(k) until all low(j) values are unique. Each resulting pair (low(j), j) defines an H_1 barcode interval [birth(low(j)), death(j)). Crucially, Ripser optimizes this via two invariants: First, by duality, cohomology persistence produces identical barcodes while operating on the transposed matrix, which processes columns in reverse order and naturally clears rows. Second, an 'apparent pair' occurs when a triangle sigma and an edge tau satisfy tau = max(boundary(sigma)) and sigma = min(coboundary(tau)) at the exact same filtration value. These pairs are guaranteed to yield zero persistence length; detecting them purely via simplex indexing allows the algorithm to discard both simplices before they ever enter the boundary matrix, dropping the effective matrix size by orders of magnitude and resolving H_1 barcodes in O(m^2) practical time and O(m) space. For the final challenge, he introduced an algebraic combinatorics and polynomial factorization task over permutation groups: "Given a permutation pi in S_n, compute its Robinson-Schensted-Knuth (RSK) correspondence—mapping pi to a unique pair of Standard Young Tableaux (P, Q) of identical shape lambda—in strict O(n log n) deterministic time, and reconstruct the length of the Longest Common Increasing Subsequence of any two sequences via the Greene-Kleitman Invariant without dynamic programming." I noted that standard Schensted row-bumping takes O(n^2) worst-case time when tableau shapes are skewed. I proposed accelerated RSK via Balanced Search Trees (Fenwick / Treap-backed Patience Sorting) combined with Viennot's Geometric Shadow Construction. The interviewer challenged me: "Walk me through Schensted's row-insertion invariant, and prove how Greene's Theorem equates the prefix sums of the Young diagram row lengths lambda_1 + ... + lambda_k to the maximum cardinality of a union of k disjoint increasing subsequences in pi." I explained that RSK inserts elements pi(1), ..., pi(n) into an initially empty tableau P: to insert x into row r, we find the smallest element y > x in row r. If such y exists, x replaces (bumps) y, and y is recursively inserted into row r + 1; if no such y exists, x is appended to the end of row r. The recording tableau Q logs the insertion step at the newly created cell. Greene's Theorem provides the fundamental structural bridge: for any permutation pi, let lambda = (lambda_1, lambda_2, ..., lambda_h) be the partition shape of its RSK tableau. For every integer k >= 1, the sum of the first k parts sum_{i=1}^k lambda_i equals the maximum size of a subset of elements of pi that can be decomposed into at most k increasing subsequences (k-increasing chains). In particular, lambda_1 is the length of the Longest Increasing Subsequence (LIS), and the conjugate partition's first column lambda'_1 is the length of the Longest Decreasing Subsequence (LDS). To execute RSK in O(n log n) time, we observe that bumping within each row is a predecessor query, which runs in O(log n) via binary search. By maintaining the boundaries of the Young diagram using Crochemore-style level-linked AVL trees or Viennot's geometric shadow lines (where coordinate projections trace shadow corners of point sets in the plane), each inserted element traces its full bumping trajectory in amortized O(log n) steps. This constructs both tableaux P and Q in strict O(n log n) deterministic time and O(n) space.