Google

The interviewer opened with an advanced linear algebra and matrix rank problem over rings: "Given an undirected simple graph G with n vertices and m edges, compute the exact number of Eulerian orientations of G modulo 998244353 in polynomial time, or determine if any exist." I noted that generating orientations naively tests 2^m directed configurations, which fails when m reaches 100. I reframed Eulerian orientations through algebraic cycle space and Laplacians over the finite field GF(2). The interviewer followed up: "An Eulerian orientation exists if and only if every vertex has even degree in the undirected graph. Once degree parities are satisfied, what algebraic invariant determines the number of valid orientations, and how do you compute it?" I explained that if any vertex has an odd degree, the count is strictly 0. If all degrees are even, we pick an arbitrary initial orientation for each edge. For each vertex v, let diff(v) = out_deg(v) - in_deg(v). An orientation is Eulerian if and only if diff(v) = 0 for all v. Reversing a directed cycle alters no vertex degrees (diff(v) remains unchanged), while reversing a directed path from u to v shifts diff(u) by -2 and diff(v) by +2. Because any Eulerian orientation can be transformed into another by reversing a collection of edge-disjoint directed cycles, the set of all Eulerian orientations forms an affine subspace over GF(2) whose dimension equals the dimension of the cycle space of G. The cycle space of a graph with c connected components has dimension exactly m - n + c. Since every element in the cycle space corresponds to a distinct orientation obtained by reversing a cycle basis, there are exactly 2^(m - n + c) valid orientations. We find the connected components via BFS/DFS in O(n + m) time, evaluate m - n + c, and compute 2^(m - n + c) mod 998244353 using fast modular exponentiation in O(log m) time and O(n + m) space. He then shifted to a computational geometry and topology challenge on planar curves: "Given a self-intersecting closed polygonal path P with n vertices in the 2D plane and a query point Q not lying on any segment of P, compute the Winding Number of P around Q in O(n) time and O(1) auxiliary space without computing trigonometric angles or inverse tangents." I pointed out that summing signed angular sweeps via atan2(y, x) introduces floating-point drift and is computationally expensive. I proposed an exact integer Crossing Number / Ray-Casting algorithm with vertical edge crossing orientation. The interviewer cut in: "Walk me through how horizontal ray casting tracks crossings, and how signed tests distinguish counter-clockwise loops from clockwise loops without edge-case singularities." I explained that we cast a horizontal ray extending from Q = (x_q, y_q) to positive infinity along the x-axis. For each directed segment from vertex A = (x_1, y_1) to vertex B = (x_2, y_2), we check whether the segment straddles the horizontal line y = y_q. To handle endpoints consistently without double-counting, we require that the crossing satisfies (y_1 <= y_q < y_2) for upward edges, or (y_2 <= y_q < y_1) for downward edges. If the segment straddles y_q, we compute the 2D cross product cross(B - A, Q - A) = (x_2 - x_1) * (y_q - y_1) - (y_2 - y_1) * (x_q - x_1). For an upward edge (y_1 <= y_q < y_2), if the point Q lies strictly to the left of the directed edge (cross product > 0), the edge crosses the ray from right to left, meaning P winds counter-clockwise around Q, so we increment winding_number by +1. For a downward edge (y_2 <= y_q < y_1), if Q lies strictly to the right of the directed edge (cross product < 0), the edge crosses the ray from left to right, meaning P winds clockwise, so we decrement winding_number by -1. Because all calculations use integer multiplications without division or trig functions, the winding number is computed in strict O(n) time and O(1) space. For the final challenge, he introduced an algebraic spectral graph problem: "Given an undirected unweighted bipartite graph G with n vertices and m edges, determine whether G is Ramanujan—meaning every non-trivial eigenvalue lambda of its adjacency matrix satisfies |lambda| <= 2 * sqrt(d - 1), where d is the average or regular degree—and outline how the non-backtracking Hashimoto matrix avoids the trivial eigenvalues caused by bipartite symmetry." I noted that directly computing all eigenvalues of the adjacency matrix A via QR decomposition takes O(n^3) time and suffers from high-degree spectral clutter. I proposed constructing the Hashimoto Non-Backtracking Matrix B and applying the Ihara-Bass Formula. The interviewer challenged me: "Define the directed edge-space of the Hashimoto matrix, explain the non-backtracking condition, and show how the Ihara-Bass determinant identity links B's spectrum back to vertex-level matrices." I broke down the construction: we replace each undirected edge with two directed edges, yielding 2m directed arcs. The Hashimoto matrix B is a 2m x 2m matrix indexed by directed arcs: entry B[(u, v), (w, z)] equals 1 if and only if v == w and z != u (the next edge departs from where the previous arrived, but does NOT immediately backtrack along the same edge), and 0 otherwise. Unlike the adjacency matrix A, whose spectrum is corrupted by local backtracking cycles (u -> v -> u), the powers of B count strictly non-backtracking closed walks, whose spectral radius directly isolates the true expansion properties of the graph. By the Ihara-Bass Formula, the characteristic polynomial of B satisfies det(I - u * B) = (1 - u^2)^(m - n) * det(I - u * A + u^2 * (D - I)), where D is the diagonal degree matrix. This identity allows us to compute the non-backtracking spectrum using only an n x n matrix polynomial rather than a 2m x 2m system, enabling iterative eigenvalue solvers like Arnoldi or Lanczos to test the Ramanujan spectral bound in O(m * poly(1 / epsilon)) time and O(n + m) space.