Amazon

The interviewer opened with an advanced tree query challenge on dynamic paths: "Given a tree of n nodes where each node has a value, answer q offline queries asking for the k-th smallest node value on the unique simple path between arbitrary vertices u and v." I pointed out that running a full path traversal takes O(q * N), and binary lifting alone cannot maintain dynamic value distributions efficiently. I proposed combining Lowest Common Ancestor (LCA) via Binary Lifting with a Persistent Segment Tree over the tree structure. The interviewer followed up: "Walk me through how persistence is propagated along tree edges rather than a linear array, and how you isolate the path [u, v] using segment tree roots." I explained that instead of building version i from version i - 1, we build the persistent segment tree for node u directly on top of the root of its immediate parent `parent[u]`, inserting u's value into the value-frequency trie. Because tree path frequencies follow prefix-sum inclusion-exclusion, the frequency of any value range on the simple path between u and v is computed in O(log N) as `count(u) + count(v) - count(lca(u, v)) - count(parent[lca(u, v)])`. Guided by these counts, we descend the persistent trees to locate the k-th smallest element in O(log N) time per query, achieving O((N + q) log N) total runtime and O(N log N) space. He then transitioned to a bit-level linear basis scenario: "Given an array of n integers, support dynamic insertions and answer queries asking for the maximum bitwise XOR sum achievable from any arbitrary subset of the numbers seen so far." I noted that generating all 2^N subsets takes exponential time, and standard dynamic programming blows up with large 64-bit integer values. I proposed maintaining a Linear Basis (Vector Space over GF(2)). The interviewer cut in: "How does the basis represent all achievable XOR combinations, and what is the insertion and maximum-query mechanism?" I explained that any set of 64-bit integers can be spanned by a basis of at most 64 non-zero numbers, where each basis element `basis[i]` has its highest set bit at position i. When inserting an incoming integer x, we iterate i from 63 down to 0: if the i-th bit of x is set and `basis[i]` is empty, we set `basis[i] = x` and break; if `basis[i]` is already occupied, we eliminate the bit by updating `x ^= basis[i]` and continue. To extract the maximum XOR sum, we initialize `max_xor = 0` and greedily transition down from bit 63 to 0, updating `max_xor = max(max_xor, max_xor ^ basis[i])`. He verified that insertions and maximum queries both complete in O(64) = O(1) time and O(64) space, approving the implementation. For the final challenge, he introduced a graph flow optimization problem: "You are given a directed network of n nodes with both edge capacities and per-unit edge traversal costs; find the minimum cost required to send a target flow amount F from source S to sink T." I explained that standard max-flow algorithms like Dinic or Edmonds-Karp only optimize capacity throughput while ignoring cost weights, and a greedy flow push risks getting trapped in suboptimal cost paths. I proposed the Successive Shortest Path (SSP) algorithm for Minimum-Cost Maximum-Flow (MCMF) using Johnson's Potentials with Dijkstra. The interviewer challenged me: "Residual networks contain backward edges with negative costs; standard Dijkstra fails on negative weights, while SPFA degrades to O(V * E) per augmentation. How do Johnson's potentials eliminate negative edges?" I explained that we maintain node potentials `pi[u]`. For any residual edge (u, v) with cost `c(u, v)`, we define the reduced cost as `c_pi(u, v) = c(u, v) + pi[u] - pi[v]`. By setting initial potentials via Bellman-Ford or topological sort, every valid residual edge maintains `c_pi(u, v) >= 0`, enabling Dijkstra with a Fibonacci or binary heap to run in O(E log V) per augmenting step. After each shortest path augmentation, node potentials are updated by `pi[u] += dist[u]`. He watched me trace potential conservation along backward edges, confirming that the entire flow F is pushed in O(F * E log V) time without negative cycle traps.