Amazon

"Given an array of N integers, process Q range updates where every element A[i] in range [L, R] is replaced by min(A[i], X), and answer range sum queries in sub-linear time": The interviewer barred standard segment trees because range-min updates cannot be maintained with ordinary lazy tags; I solved it using Segment Tree Beats (Ji Driver technique), augmenting tree nodes with the maximum value, the strictly second maximum value, and the count of maximums, proving that amortized complexity drops to O((N + Q) log N) by restricting tag propagation strictly to nodes where second_max < X < max. "Given an undirected weighted graph, answer offline queries asking for the number of connected components formed by edges with weight at most W, with dynamic edge additions and deletions interleaved between queries": The interviewer pushed past standard Disjoint Set Union (DSU) since deletions break standard path compression; I resolved it by applying Divide and Conquer over Time with a dynamic Segment Tree over the offline query timeline, pushing each edge's lifespan into canonical time intervals, and walking the timeline tree using a persistent/rollback DSU with union-by-rank to revert state transitions in O(log N) per timeline backtrack. "Given a rooted tree of N nodes where each node has a color, answer Q sub-tree queries asking for the number of distinct colors appearing at least K times within node v's subtree": The interviewer rejected an O(N^2) DFS traversal and demanded an O(N log N) or O(N log^2 N) solution with minimal memory overhead; I resolved it via DSU on Tree (Sack technique), classifying child edges into light and heavy, preserving the heavy-child frequency state in place across DFS calls while clearing and re-adding light subtrees, and maintaining a fenwick tree over color frequencies to resolve threshold counts in O(N log^2 N) overall time.