Amazon

"Given an array of N integers, process Q range affine transformations where each element A[i] in [L, R] is replaced by (A[i] * B + C) mod M, while supporting historical rollback queries to any past state t in O(log N) time": The interviewer barred rebuilding the tree per update due to memory exhaustion; I solved it by designing a Fully Persistent Segment Tree with fractional cascading and lazy node-cloning, where modification paths allocate fresh child pointers on write while deferring affine coefficient compositions via immutable fat-tags to retain strict O(log N) space and time complexity per revision. "Given an undirected network with N nodes and dynamic edge costs, maintain the All-Pairs Shortest Path (APSP) matrix across arbitrary single-edge weight increases and deletions in sub-cubic time": The interviewer rejected re-running Dijkstra from all sources ($O(V \cdot E \log V)$) on every update; I formulated a dynamic graph solution using Demetrescu-Italiano decremental APSP maintenance, tracking historical shortest-path DAGs and historical bottleneck edges to update only the affected pairwise subtrees, bounding total amortized update time to $O(V^2 \log V)$ across arbitrary sequences of weight increments. "Given a massive text of length N, answer online point-location and pattern occurrence queries for dynamic patterns, where characters are periodically inserted and removed inside the text": The interviewer pointed out that static Suffix Automata and Aho-Corasick trees require complete structural rebuilds upon internal text mutations; I addressed this by coupling an implicit Splay-Tree-based Balanced Treap over the string sequence with a dynamic Suffix-Tree via Ukkonen’s algorithm augmented by dynamic tree (Link-Cut Tree) parent pointers, preserving suffix link invariants during internal node splits and merges in amortized $O(\log^2 N)$ per modification.