Route Between Nodes: Given a directed graph, design an algorithm to find out whether there is a route between two nodes.

This problem can be solved by just simple graph traversal, such as depth-first search or breadth-first search. We start with one of the two nodes and, during traversal, check if the other node is found. We should mark any node found in the course of the algorithm as “already visited” to avoid cycles and repetition of the nodes.

It may be worth discussing with your interviewer the tradeoffs between breadth-first search and depth-first search for this and other problems. For example, depth-first search is a bit simpler to implement since it can be done with simple recursion. Breadth-first search can also be useful to find the shortest path, whereas depth-first search may traverse one adjacent node very deeply before ever going onto the immediate neighbors.

• Depth-First Search
• Breadth-First Search
• Bidirectionnal Breadth-First Search

Depth-First

Virtually all candidates who aren’t well versed in graph theory take this approach, probably because it most closely models how they themselves would solve this kind of problem.

Avoid infinite loops by keeping track of the visited profiles.
Knowing when to stop descending down a branch (i.e., you have found a solution, or there isn’t one).

If you are trying to find the shortest path using a depth-first search:

• Keep track of the “best answer so far” and stop going down a branch if it has become longer than that best answer.
• You need to save visited profiles as well as how many steps it took to visit a profile. And continue if the current solution has arrived at that profile in fewer steps.

Breadth-First

This could also be called a degenerate form of Dijkstra’s Algorithm, where the edge weights are the same (positive, non-zero) value.

Bidirectional Breadth-First

Same as before, but we start searching from both ends at the same time and stop as soon as we find a common profile in both search trees. Improvement comes from the fact that two circles with radius r have a smaller total area than 1 big circle with radius 2r.

The complexity of naive BFS for two people N connections apart in the network with M connections per person on average is O(M^N), while the complexity of bidirectional search will be O(M^(N/2)).