Amazon

"Given a dynamic forest of nodes where edges are added and removed in real time, answer path-maximum and node-connectivity queries in sub-linear time": The interviewer barred standard DFS/BFS traversals due to continuous edge mutations; I solved it by implementing a Link-Cut Tree (LCT), representing the dynamic trees as splay trees over heavy-light preferred paths, and walked through the `access(u)`, `link(u, v)`, and `cut(u, v)` primitives with aggregate path maintenance to achieve amortized O(log N) operations per update and query. "Given an array of N integers, answer Q queries finding the most frequent element (mode) within an arbitrary subarray range [L, R] strictly in offline linear-subquadratic time": The interviewer pointed out that segment trees cannot maintain dynamic range mode efficiently; I framed the solution using Mo’s Algorithm with square-root block decomposition ($O(N \sqrt{N})$), maintaining frequency tables and a frequency-of-frequencies count array, and walked through removing the $O(\sqrt{N})$ inner bottleneck using a rollback square-root decomposition technique to support non-invertible data structures without dynamic tree overhead. "Given a collection of N strings with total length M, process online updates that append characters to strings and answer queries asking for the longest common substring between any two specified strings": The interviewer rejected static suffix arrays due to dynamic appends; I solved it by constructing a Generalized Suffix Automaton (GSAM) built online via directed acyclic word graph (DAWG) link additions, maintaining parent links with dynamic lowest common ancestor (LCA) queries over heavy-light decomposition to evaluate substring containment and match lengths in O(|s|) query time.