Google

The interviewer opened with an online string indexing challenge: "Construct a data structure over an alphabet that processes a text stream one character at a time, such that after each appended character, you can report the total number of distinct substrings in the entire text in amortized constant time." I explained that rebuilding a Suffix Automaton or Suffix Array from scratch on every character takes O(N^2) or O(N log N) overall, which is too slow for real-time streaming. I proposed an Online Suffix Automaton (SAM). The interviewer followed up: "Walk me through what happens when an incoming character causes a transition collision, and how you adjust the distinct substring count without a full tree re-traversal." I broke down the state mechanics: each state u in a SAM represents an equivalence class of substrings with identical end-positions and contributes `len[u] - len[link[u]]` distinct substrings to the total count. When appending a character c, we create a new state `cur` with `len[cur] = len[last] + 1` and trace backward along suffix links from `last`. If we hit an ancestor `p` that already has a transition on c to some state `q`, we check whether `len[q] == len[p] + 1`. If it is, we simply link `cur` to `q` and increment our global distinct substring counter by `len[cur] - len[q]`. If `len[q] > len[p] + 1`, state `q` must be split: we clone `q` into a new state `clone` with `len[clone] = len[p] + 1`, copy transitions, redirect the forward edges from `p` and its ancestors from `q` to `clone`, and repoint the links of both `q` and `cur` to `clone`. Crucially, because `clone` merely partitions the equivalence class of `q`, the split introduces zero net change to the substring count; only the newly added state `cur` contributes `len[cur] - len[link[cur]]`. He verified that the three pointer redirections run in amortized O(1) time per character, proving the online counter runs in strict O(N) total time and O(N * alphabet) space. He then shifted to a computational geometry and space-partitioning problem: "Given n stationary points (sites) in a 2D plane, compute their Voronoi Diagram—partitioning the plane into regions closest to each site—in O(N log N) time without building the dual Delaunay Triangulation first." I ruled out discrete grid distance transforms because they are approximations and scale with grid resolution rather than site count. I proposed Fortune's Sweep-Line Algorithm. The interviewer cut in: "A sweep-line normally maintains linear segments, but a sweep-line over points produces parabolic arcs; explain the beachline invariant and how circle events eliminate arcs." I explained that as a horizontal sweep-line moves downward, the locus of points equidistant from a site above the line and the line itself forms a parabola. The lower envelope of these parabolas is called the beachline. We maintain the beachline as a Balanced Binary Search Tree (BBST) where internal nodes represent breakpoints between adjacent parabolic arcs and leaves represent the arcs themselves. The algorithm processes two discrete priority queue events: site events (when the sweep-line hits a new site, creating a new parabolic arc that splits an existing one in the beachline) and circle events. A circle event occurs when three adjacent parabolic arcs on the beachline define a circle tangent to the sweep-line. As the sweep-line reaches the bottom of this tangent circle, the middle parabolic arc shrinks to a single point and vanishes. At that exact coordinate, a new Voronoi vertex is formed where three Voronoi cell edges meet, and the middle arc is deleted from the BBST. Because each site insertion creates at most two new arcs and each circle event eliminates one, at most O(N) events are ever scheduled. Processing each event via the BBST takes O(log N) time, completing the exact diagram in O(N log N) time and O(N) memory. For the final challenge, he introduced a graph sparsification and distance-preserving metric: "Given a connected undirected graph with n vertices and m weighted edges, compute an alpha-spanner of the graph—a sparse subgraph with at most O(n^(1 + 2 / (2k - 1))) edges such that the shortest path distance between any two vertices in the spanner is at most (2k - 1) times their shortest path distance in the original graph—in polynomial time." I pointed out that finding a Minimum Spanning Tree yields only n - 1 edges, but its stretch factor (distortion) can be as bad as Omega(n) on cycle graphs. I proposed the Baswana-Sen Randomized Greedy Spanner Algorithm (or the Althofer Greedy Spanner). The interviewer challenged me: "Let's focus on the Althofer Greedy Spanner. Walk me through the greedy edge-selection invariant, and prove why the resulting subgraph preserves the (2k - 1) stretch factor without retaining short cycles." I broke down the selection rule: we sort all m edges in non-decreasing order of their weights. We initialize an empty spanner subgraph H = (V, empty_set). For each edge e = (u, v) with weight w(u, v) in sorted order, we compute the shortest path distance between u and v in our current spanner H: if dist_H(u, v) > (2k - 1) * w(u, v), we must add edge e to H; otherwise, the existing paths in H already approximate the distance between u and v within the factor (2k - 1), so edge e can be safely discarded. By construction, any cycle formed in H must contain at least 2k + 1 edges, meaning the girth of H is strictly greater than 2k. According to the Bondy-Simonovits Theorem and the Moore bound on extremal graph theory, any n-vertex graph with girth > 2k contains at most O(n^(1 + 1/k)) edges. Running Dijkstra to test dist_H(u, v) for each candidate edge constructs the spanner in O(m * (m + n log n)) time, producing a provably sparse subgraph with bounded distortion.