Find Closest Node to Given Two Nodes

Find Closest Node to Given Two Nodes

What is this problem about?

The Find Closest Node to Given Two Nodes interview question provides a directed graph where each node has at most one outgoing edge. You are given two starting nodes, node1 and node2. Your goal is to find a node $X$ that is reachable from both starting nodes such that the maximum of the distances from node1 to $X$ and from node2 to $X$ is minimized. If there's a tie, return the node with the smallest index.

Why is this asked in interviews?

Amazon and Google use this problem to test your ability to coordinate multiple traversals. It evaluation your proficiency with Breadth-First Search (BFS) or Depth-First Search (DFS) and your ability to store and compare path information. It’s a great test of "Min-Max" optimization—where you want to find the best among the worst-case scenarios.

Algorithmic pattern used

This problem uses Multi-source Distance Tracking.

1. Perform a traversal from node1 to calculate the distance to all reachable nodes. Store these in an array dist1.
2. Perform a traversal from node2 to calculate the distance to all reachable nodes. Store these in an array dist2.
3. Iterate through all nodes $i$ from 0 to $n-1$:
   • If node $i$ is reachable from both (dist1[i] != -1 and dist2[i] != -1):
     • Calculate max_dist = max(dist1[i], dist2[i]).
     • Update the global minimum max_dist and the corresponding node index.

Example explanation

Edges: [2, 2, 3, -1] (0->2, 1->2, 2->3, 3 has no edge). Starting nodes: 0 and 1.

1. From node 0: 0 $o$ 2 (dist 1), 2 $o$ 3 (dist 2). dist1 = [0, -1, 1, 2].
2. From node 1: 1 $o$ 2 (dist 1), 2 $o$ 3 (dist 2). dist2 = [-1, 0, 1, 2].
3. Reachable from both:
   • Node 2: max(1, 1) = 1.
   • Node 3: max(2, 2) = 2.
4. Minimum max_dist is 1, found at Node 2. Result: 2.

Common mistakes candidates make

• Single traversal: Trying to find the node in a single BFS, which doesn't allow for the min-max comparison.
• Not handling cycles: Since each node has only one outgoing edge, the graph is a collection of functional components (paths ending in cycles). Failing to handle infinite loops in your traversal is a common error.
• Index ties: Forgetting to return the smallest index when multiple nodes yield the same minimum max-distance.

Interview preparation tip

When a problem asks to minimize the maximum of two distances, always calculate all distances from both sources independently first. This "Precompute and Intersect" strategy is a common Graph interview pattern.