This question is similar to the “Route Between Nodes” from this book.
Consider a popular social networking website, Facebook for example. People can create their own profile and add friends.
Given two Facebook profiles, I want to find out how to get from profile A to profile B starting from A's friends. Output all profiles "in-between" the two profiles.
Make sure you are building up the return value and not just returning true.
Interviewers avoid saying the word “path” in the initial question as this can be a direct prompt to consider the question as a graph question.
Clarify if you need to return the shortest path or not.
This is a graph problem. A full solution involves generating the graph, plus a path searching algorithm.
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
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.
This could also be called a degenerate form of Dijkstra’s Algorithm, where the edge weights are the same (positive, non-zero) value.
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)).
This is covered at length in this interview prep book.