Amazon

The interviewer opened with an advanced tree link-cut scenario: "Design a data structure to maintain a dynamic forest of trees supporting edge insertions, edge deletions, and queries for the path aggregate between any two connected vertices in logarithmic time." I pointed out that Heavy-Light Decomposition handles path queries on static trees in O(log^2 N) time but cannot support dynamic structural mutations like edge cuts and links without full tree recomputations. I proposed a Link-Cut Tree (LCT) built on Splay Trees. The interviewer followed up: "Explain preferred children, preferred paths, and how the core access(u) operation brings a node into the root path." I explained that the original trees are partitioned into disjoint preferred paths represented as auxiliary Splay trees keyed by node depth. Calling `access(u)` splays node u to the root of its current auxiliary tree, switches its right child to a path-parent pointer (disconnecting deeper nodes), and ascends through path-parent pointers to splice u into a single preferred path originating at the root of the represented tree. With `access(u)`, `link(u, v)` and `cut(u, v)` reduce to simple splay pointer updates, while path reversals via lazy tags handle `make_root(u)`. He had me trace the amortized potential analysis, proving all operations run in amortized O(log N) time and O(N) space. He then shifted to string indexing and full-text substring queries: "Given a string s of length n over a constant alphabet, construct an index in linear time that can count and locate all occurrences of any query pattern p in O(|p|) time, while maintaining minimum auxiliary space." I noted that Suffix Trees achieve optimal query time but suffer heavy constant factors and node overhead (often 20 to 40 bytes per character), while Suffix Automata represent substrings without explicit suffix sorting. I proposed constructing the Suffix Array paired with the LCP (Longest Common Prefix) array using Kasai's Algorithm, or alternatively a Suffix Automaton (SAM). The interviewer cut in: "Let's focus on the Suffix Automaton. Explain its Directed Acyclic Word Graph (DAWG) structure, define the end-position equivalence class `endpos(t)`, and show why it has at most 2n - 1 states and 3n - 4 transitions." I explained that two substrings belong to the same state if and only if they share identical sets of right-end occurrence positions in s. Because any two `endpos` sets are either completely disjoint or one is a strict subset of the other, the state relations form a tree hierarchy known as the link tree. I walked through the online linear construction algorithm, inserting characters one by one and cloning split states when transition lengths exceed link-depth continuity. He had me trace the pattern matching transitions, verifying strict O(n) construction time and O(|p|) lookup bounds. For the final challenge, he introduced a combinatorial matrix enumeration problem: "Given an undirected simple graph G with n vertices and m edges, compute the exact number of distinct spanning trees in the graph in polynomial time." I noted that generating all subgraphs or testing combinations via cycle-detection or DSU takes exponential O(2^m) time, which is completely intractable when n reaches 100. I proposed applying Kirchhoff's Matrix Tree Theorem. The interviewer challenged me: "Walk me through the exact formulation of the Laplacian matrix, and explain how the determinant of any arbitrary cofactor yields the number of spanning trees without overcounting." I broke down the algebraic construction: we construct the n x n Laplacian matrix `L = D - A`, where `D` is the diagonal degree matrix (`D[i][i] = degree(v_i)`) and `A` is the adjacency matrix (`A[i][j] = 1` if edge (i, j) exists, else 0). By the Matrix Tree Theorem, deleting any single row i and its corresponding column i yields an (n - 1) x (n - 1) reduced Laplacian cofactor matrix `L_red`. The determinant `det(L_red)` equals the exact number of spanning trees. To compute this determinant efficiently without precision blowup or exponential expansion, I implemented Gaussian Elimination over floating-point or modular arithmetic, using row additions and pivots to reduce `L_red` to upper triangular form in O(n^3) time. The product of the main diagonal elements gives the determinant, completing the entire count in O(n^3) time and O(n^2) space.