Google

The interviewer opened with an advanced shortest-path query challenge under geometric constraints: "Given a simple polygon P with n vertices and two query points s and t lying in its interior, compute the Euclidean Shortest Path between s and t completely contained within P in O(n) time, without constructing the full O(n^2) visibility graph." I pointed out that constructing a general visibility graph takes O(n^2), which degrades point-to-point queries for n = 2 * 10^5. I proposed using Lee-Preparata's Funnel Algorithm over a Triangulated Polygon Sleeve. The interviewer followed up: "Walk me through how a dual tree of the triangulation extracts a sleeve, and explain the geometric invariant of the apex and two convex boundaries that allows the funnel to advance in linear time." I explained that we first triangulate P in O(n) time using Chazelle’s algorithm (or O(n log n) via monotone decomposition). The dual graph of the triangulation forms a tree where each node is a triangle and edges represent shared diagonals. The unique tree path between the triangle containing s and the triangle containing t defines an ordered sequence of triangles called a sleeve, bounded by an alternating chain of internal diagonals. The shortest path from s to any point across these diagonals is constrained by an active 'funnel'—a structure consisting of an apex vertex and two inward-convex polygonal chains extending from the apex to the two endpoints of the current internal diagonal. As we advance from diagonal d_k = (L_k, R_k) to diagonal d_{k+1}, one endpoint is shared while the other changes (say, moving from R_k to R_{k+1}). We update the right convex chain by popping vertices that violate convexity (tested via 2D cross-product orientation). If the new endpoint crosses past the left chain, the funnel collapses: the apex steps forward along the left chain to the last tangent vertex, which is appended directly to the output shortest path, and a new funnel opens from that new apex. Because each vertex enters and leaves the funnel at most once, the entire shortest path is traced in strict O(n) time and O(n) space. He then shifted to an online randomized spatial query engine: "Given an arbitrary sequence of 2D line segments inserted one by one, maintain a Point Location structure that answers 'which face contains query point q' in O(log n) expected query time, while bounding the total structure size to O(n) in expectation." I pointed out that balanced binary planar subdivisions (like Kirkpatrick's hierarchical triangulation) require offline preprocessing of the entire planar map, failing on dynamic edge streams. I proposed Seidel’s Randomized Incremental Construction of a Trapezoidal Map backed by a Directed Acyclic Graph (DAG) search structure. The interviewer cut in: "When inserting a line segment s that cuts across multiple existing trapezoids, how do you locate all intersecting trapezoids in the DAG, and why does randomized insertion order guarantee O(log n) query depth?" I explained that the plane is partitioned into trapezoids with horizontal top and bottom bounding segments and vertical left and right bounding walls passing through segment endpoints. When a new segment s is inserted, we locate its left endpoint in the current search DAG in O(depth) time, then thread s through the existing trapezoidal map by tracing along its segment until reaching its right endpoint. Each trapezoid intersected by s is deleted and replaced by at most four new sub-trapezoids (created by dropping vertical rays from endpoints and splitting along s). In the search DAG, the leaf nodes corresponding to deleted trapezoids are converted into internal decision nodes (x-nodes that compare against endpoints, or y-nodes that test whether a point lies above or below segment s), whose outgoing edges point to the newly formed replacement trapezoids. By randomized incremental construction, backward analysis proves that at step i, the probability that a particular trapezoid was created by the i-th inserted segment is at most 4 / i. Thus, the expected number of structural modifications at step i is O(1), bounding the total DAG size to O(n) expected nodes and the expected query path depth to sum_{i=1}^n O(1 / i) = O(log n). For the final challenge, he introduced an algebraic combinatorial string scenario: "Given an integer array a_1, a_2, ..., a_n, find the length of the longest contiguous subsegment whose elements can be permuted to form a k-th power word (where every distinct value appears a number of times that is a multiple of k), in optimal O(n) expected time or O(n log n) deterministic time." I noted that checking all O(n^2) subsegments naively by counting element frequencies takes O(n^3) or O(n^2) time, which chokes when n = 10^5. I proposed reducing the frequency parity constraints to a Vector Zero-Sum Problem over the cyclic group (Z_k)^sigma, implemented via 64-bit Randomized Vector Hashing. The interviewer challenged me: "Walk me through how randomized modular vectors map the k-divisibility condition to a prefix collision test, and prove why 128-bit hashes prevent false-positive anagram matches." I broke down the algebraic reduction: an interval [L, R] can have its elements rearranged into a k-th power word if and only if for every distinct value v in the subsegment, cnt_v(R) - cnt_v(L - 1) = 0 (mod k), which is equivalent to cnt_v(R) = cnt_v(L - 1) (mod k) for all distinct values simultaneously. Instead of storing unbounded dimension vectors, we assign each unique value v a fixed, independent random signature vector r_v = (w_{v, 1}, w_{v, 2}) where weights are drawn uniformly from [1, 2^64 - 1]. We define the running prefix hash state H(t) = sum_{i=1}^t r_{a[i]} component-wise modulo k. An interval [L, R] satisfies the condition if and only if H(R) == H(L - 1). We maintain a hash table or balanced search tree storing the earliest index where each prefix hash H(t) was observed. For each prefix t from 1 to n, we look up whether H(t) has been seen before: if it exists at index t_old, then the subarray [t_old + 1, t] is valid, and its length is t - t_old. Tracking the maximum length across all prefixes resolves the problem in strict O(n) expected time using `std::unordered_map` and O(n) space, with collision probability bounded below 2^(-64) by the Schwartz-Zippel Lemma over Z_k.