Google

The interviewer opened with an advanced tree query and online dynamic diameter scenario: "Given an initially empty graph of n vertices, process an online sequence of edge additions that construct a forest. After each edge addition that connects two disjoint trees into a single tree, report the diameter of the newly merged component in O(1) or amortized O(alpha(n)) time." I observed that running a two-pass BFS/DFS after every merge takes O(V + E), which degrades to quadratic time across an edge stream. I proposed maintaining the diameter endpoints of each connected component using Disjoint Set Union (DSU) paired with Lowest Common Ancestor (LCA) queries via Binary Lifting. The interviewer followed up: "Prove why the diameter of the union of two merged trees must have its endpoints chosen exclusively from the endpoints of the original two diameters." I explained that for any tree T, the farthest node from any arbitrary vertex x is always one of the two endpoints of T's diameter (call them {u1, v1}). When tree T1 with diameter endpoints (u1, v1) and tree T2 with diameter endpoints (u2, v2) are linked by an edge, the maximum simple path in the merged tree must either remain an internal path inside T1, an internal path inside T2, or cross the new edge connecting a node in T1 to a node in T2. Due to the metric tree property, the longest cross-tree path must connect one of {u1, v1} to one of {u2, v2}. Thus, the new diameter endpoints are guaranteed to be one of the six pairwise combinations: (u1, v1), (u2, v2), (u1, u2), (u1, v2), (v1, u2), or (v1, v2). By querying tree distances dist(x, y) = depth[x] + depth[y] - 2 * depth[lca(x, y)] in O(log N) or O(1) via Euler Tour RMQ, we evaluate all 6 candidate distances and update the component's diameter endpoints in DSU in O(log N) time and O(N) space. He then shifted to an offline range query optimization on trees: "You are given a tree of n vertices where each node has a color, and q offline path queries asking for the number of distinct colors appearing along the simple path between arbitrary vertices u and v." I pointed out that HLD with segment trees incurs O(q * log^2 N) with heavy set-merging overhead, while naive path traversals take O(q * N). I proposed Tree Mo's Algorithm via Euler Tour (Flattening the Tree into a 1D sequence). The interviewer cut in: "Walk me through how tree paths are mapped to contiguous 1D subsegments of the Euler Tour, and why the Lowest Common Ancestor must be handled separately when u is not an ancestor of v." I explained that we record an Euler Tour where each node x appears twice: `first[x]` when the DFS enters x, and `last[x]` when the DFS exits x. Assuming without loss of generality that `first[u] <= first[v]`: if u is an ancestor of v, the path between them corresponds directly to the range `[first[u], first[v]]`. In this range, any node lying off the path appears both on entry and exit (twice), while nodes on the path appear exactly once. However, if u is not an ancestor of v, the path maps to `[last[u], first[v]]`. In this interval, the LCA node `lca(u, v)` never appears because the DFS entered it before `last[u]` and exits it after `first[v]`. Therefore, we process the 1D range `[last[u], first[v]]` using standard Mo's sorting by block size B = N / sqrt(q), toggling a node's inclusion in our frequency state whenever its appearance count hits 1 versus 0/2, and temporarily adding `lca(u, v)`'s color before recording the query answer. This guarantees exact distinct color counts in O((N + q) * sqrt(N)) time and O(N) auxiliary space. For the final challenge, he introduced an algebraic combinatorial graph problem: "Given an undirected simple graph G with n vertices and m edges, determine whether the graph contains a triangle (a 3-cycle) in strictly sub-cubic time, and find the minimum-weight triangle if edge weights are present." I noted that checking all triples takes O(n^3), which TLEs when n reaches 4000. I proposed fast Boolean Matrix Multiplication or the Node Degree Partitioning (Heavy-Light Vertex) technique. The interviewer challenged me: "Let's focus on the degree-partitioning approach because it requires no matrix multiplication overhead and runs in O(m * sqrt(m)) time. Walk me through the directed acyclic graph (DAG) orientation and neighbor-intersection steps." I broke down the algorithm: we orient every undirected edge (u, v) into a directed edge u -> v if `deg(u) < deg(v)`, or if `deg(u) == deg(v)` and `u < v`. This edge orientation guarantees that the resulting directed graph is a DAG, and more importantly, every vertex has out-degree at most O(sqrt(m)). To find triangles, we iterate through all vertices u. For each directed edge u -> v, we mark all out-neighbors w of u in a boolean array or hash table. Then, for each out-neighbor v of u, we iterate through all directed out-neighbors w of v; if w is already marked as an out-neighbor of u, the directed paths u -> v -> w and u -> w confirm a triangle {u, v, w}. Because every directed edge v -> w is traversed at most once for each in-neighbor u of v, and the maximum out-degree is bounded by O(sqrt(m)), the total number of operations across all edges is bounded by sum_{e=(u,v)} min(out_deg(u), out_deg(v)) <= m * sqrt(m). When edge weights are present, we simply track min(weight(u, v) + weight(v, w) + weight(u, w)) during the intersection check, identifying the minimum-weight triangle in strict O(m * sqrt(m)) time and O(n + m) space.