Amazon

The interviewer opened with an advanced linear algebra state-space optimization: "Given a 2-SAT problem with n boolean variables and m clauses in Conjunctive Normal Form (CNF), determine whether a satisfying assignment exists, and if so, construct a valid truth assignment." I immediately pointed out that 3-SAT is NP-complete, but 2-SAT can be reduced to directed graph reachability in linear time. The interviewer followed up: "Walk me through how an implication graph is constructed from each clause (x OR y), and what graph property mathematically proves unsatisfiability?" I explained that each clause (x OR y) is equivalent to two directional implications: (NOT x => y) and (NOT y => x). We construct a directed implication graph with 2n vertices (representing each variable and its negation). Using Tarjan's or Kosaraju's algorithm, we compute the Strongly Connected Components (SCCs). A satisfying assignment is impossible if and only if any variable x and its negation NOT x belong to the exact same SCC, because that implies x => NOT x and NOT x => x simultaneously. If no such conflict exists, a valid assignment is constructed in topological order of the condensed SCCs by assigning true to whichever literal's component appears later in the topological sort. He had me code the component grouping and verified the O(V + E) = O(n + m) time and memory bound. He then shifted to computational geometry on large point sets: "Given n points in a 2D plane, find the pair of points with the smallest Euclidean distance between them in sub-quadratic time." I noted that the brute-force pairwise check takes O(N^2), which fails when n reaches 10^5. I proposed a Divide and Conquer approach. The interviewer cut in: "When merging the left and right halves separated by a vertical dividing line, checking all pairs across the boundary takes O(N^2) again—how do you guarantee sub-quadratic execution across the middle strip?" I explained that we first sort all points by x-coordinate, split the set at median x into left and right subsets, and recursively find the minimum distances `d_left` and `d_right`, setting `d = min(d_left, d_right)`. For the merge step, we only collect points lying within distance d of the vertical dividing line `[mid_x - d, mid_x + d]`. Crucially, when sorted by y-coordinate within this strip, geometric packing bounds dictate that for any given point, at most 7 subsequent points can possibly lie within a distance smaller than d without violating the definition of d. Therefore, the inner comparison loop runs at most 7 iterations per point. By maintaining y-sorted order during recursion via Merge Sort rather than re-sorting, the recurrence resolves to T(N) = 2T(N/2) + O(N), yielding strict O(N log N) time and O(N) space. For the final challenge, he introduced a tree structural decomposition problem: "Given a tree of n nodes where each node has a weight, answer queries asking whether there exists a simple path in the tree whose total weight equals a target integer S." I observed that processing paths through standard tree DP takes O(N^2) or higher when paths cross arbitrary subtrees. I proposed Centroid Decomposition. The interviewer challenged me: "Define a tree centroid, explain how recursively decomposing at centroids yields a balanced centroid tree of logarithmic height, and show how path queries are combined without double-counting." I explained that a centroid is a node whose removal partitions the tree into disconnected components, each containing at most N/2 nodes. By repeatedly finding the centroid in O(component_size) via DFS, making it a root in the centroid tree, and recursing on the remaining subtrees, the centroid tree has a strict maximum depth of O(log N). To process paths passing through the current centroid C, we run a DFS into each subtree hanging off C, collecting prefix path sums, checking against a hash table of previously visited branches to see if `target - current_sum` exists, and then merging the new branch's paths into the hash table. This prevents double-counting paths that originate and terminate within the same child branch. Once done, C is deleted, and the process repeats on the sub-components. He approved the divide-and-conquer logic, proving the overall algorithm runs in O(N log^2 N) time and O(N) auxiliary space.