Interview Question for Software Engineering Intern at Google:

do breadth first search from both ends at the same time. Keep a set of all nodes that each has reached. When the sets have any element in common, there is a path.

Does the above method have any advantage over the method in which we do bfs from one node of the nodes and stop when the other node is reached?

BFS from both sides is massively faster than just doing BFS from one. Suppose each person has k friends and that the two nodes are d apart. BFS from one node is O(k^d). BFS from both nodes is O(k^(d/2)) -- the exponent is half as big.

To put some example numbers on it, if each person has 100 friends and they are 10 apart, then BFS from one node takes 10^20 operations, whereas BFS from both nodes is 2*100^5= 200 billion operations. BFS from one node is intractable. BFS from both nodes is slow, but tractable.

How about using Dijkstra's shortest path algorithm? Isn't that more efficient than a bfs?

If you only care about the distance between two nodes and every edge length is 1 (both of which are true in this problem), then Dijkstra's shortest path algorithm basically is breadth first search (and BFS from both sides is faster than a simple BFS).

If that doesn't make sense, then explain how http://en.wikipedia.org/wiki/Dijkstra's_algorithm#Pseudocode is different from a breadth first search in this case and I will clarify.

Aren't you ignoring the time taken for checking for a common element in the two sets (which will be O(k^d))?