Google

The interviewer opened with an advanced linear algebra and polynomial recovery challenge: "You are given a black-box sequence generating machine; find the shortest linear recurrence of order L (where L <= N/2) that generates a given prefix of n terms a_0, a_1, ..., a_{n-1} over a finite field Z_p in O(n^2) time." I pointed out that setting up an n x n Hankel matrix and solving it via Gaussian Elimination requires O(n^3) time, which chokes when n = 5000. I proposed the Berlekamp-Massey Algorithm. The interviewer followed up: "Walk me through how the discrepancy value delta is computed at each step, and how an older failure polynomial is scaled and shifted to update the minimal polynomial." I explained that we iteratively construct a connection polynomial C(x) = 1 + c_1 * x + ... + c_L * x^L. For the current term a_m, we compute the discrepancy delta = sum_{i=0}^L (c_i * a_{m-i}). If delta == 0, the current recurrence already predicts a_m correctly, so we proceed to m + 1. If delta != 0, our polynomial fails; we must correct it by adding a scaled and shifted version of an earlier candidate polynomial B(x) that also failed at an earlier step m_0 with discrepancy delta_0. The correction takes the form C(x) = C(x) - (delta / delta_0) * x^{m - m_0} * B(x). Crucially, we update the recorded failure state (B(x) = C(x), delta_0 = delta, m_0 = m) if and only if 2 * L <= m, which forces the degree of C(x) to expand to m + 1 - L. He watched me trace an 8-term Fibonacci-like recurrence over modulo 998244353, verifying that the nested updates perform at most O(n^2) field operations with O(n) space. He then shifted to a computational geometry and continuous ray-shooting challenge: "Given a set of n non-intersecting line segments in a 2D plane and a viewer standing at a point source P, compute the 2D visibility polygon—the exact continuous sub-region illuminated by P—in optimal O(n log n) time." I noted that casting rays toward a discrete grid of points leaves jagged gaps and takes O(grid_size), while naive ray-segment intersection checks take O(n^2). I proposed an Angular Radial Sweep Algorithm. The interviewer cut in: "How does the active segment ordering change during a 360-degree radial sweep, and how do you prevent self-intersecting false boundaries?" I broke down the event processing: we translate the coordinate system so that the light source P sits at the origin (0, 0). Each segment is decomposed into two angular endpoint events: a start event and an end event based on counter-clockwise polar angle theta in [0, 2*pi). The sweep-ray rotates around the origin from 0 to 2*pi, maintaining an active set of intersected segments in a Balanced Binary Search Tree (like `std::set`). The key ordering invariant inside the BBST is radial distance along the current sweep-ray: segment A is 'closer' than segment B if the ray at angle theta strikes A before B. When a segment's start angle is hit, it is inserted into the set; when its end angle is hit, it is removed. The illuminated boundary vertex at any instant is dictated by the intersection of the sweep-ray with the nearest active segment (the root/minimum element of the BBST). Whenever the nearest segment changes (either by insertion of a closer segment, deletion of the current blocker, or an endpoint passing), we emit a new vertex in the visibility polygon. By splitting segments that cross the positive x-axis (angle 0) so no segment wraps around the boundary, all events are processed cleanly in O(n log n) time and O(n) space. For the final challenge, he introduced an algebraic combinatorial string problem: "Given an alphabet of size k and a positive integer n, construct a cyclic sequence of minimum length such that every possible string of length n over the alphabet appears as a contiguous substring of length n exactly once." I identified this immediately as constructing a De Bruijn Sequence B(k, n) of order n, which must have length exactly k^n because there are k^n distinct strings of length n. I ruled out greedy backtracking with visited hash sets because it gets trapped in dead ends and runs in exponential time. I reframed the construction as finding an Eulerian Circuit in a directed graph. The interviewer challenged me: "Define the vertices and directed edges of the De Bruijn Graph, and explain how Hierholzer's Algorithm traverses the circuit in linear time without stack blowup." I explained that vertices represent all k^{n-1} strings of length n - 1 over the alphabet. A directed edge exists from vertex u to vertex v with label c if appending character c to u and dropping u's first character yields v: that is, u[1...n-2] + c == v. This means every directed edge uniquely represents an n-length string u + c. In this graph, every vertex has in-degree exactly equal to out-degree (both equal to k), guaranteeing that the graph is Eulerian. We construct the sequence by running Hierholzer's Algorithm: we start at an arbitrary node (like string "00...0"), greedily follow unused outgoing edges, and whenever a cycle closes, we backtrack along the path, splicing in unvisited sub-cycles until all k^n edges are traversed. Emitting the edge labels along this Eulerian path yields the circular sequence in optimal O(k^n) time and O(k^{n-1}) memory.