Connect to FB Profile

Question

I tried to find the answer to one of the problems of my interview. But did not receive a decision. Can anyone help me on this. Here is the problem Description:

Given two people, the names A and B. You know that both exist on FB. You must say whether there is a connection between them. If connectivity exists, you must specify the exact connection path. By Connectivity, they mean that B can be a friend of C, which is a friend of A. Thus, re is a connection between A and B, and the path will be A → B-> C

Answer 1

You can use bidirectional search .

Main idea:

• AGroup = {A}, BGroup = {B}.

• while intersect (AGroup, BGroup) = empty set:

  2.1 Expand each person from a group that you have not yet expanded, and paste the result into the AGroup.

  2.2 Expand each person from a group that you have not yet expanded, and paste the result into the group.

  2.3, if AGroup and BGroup have not changed, return "A and B are not connected."

• Designate S in both the AGroup and the BGroup.

Now you have a path from A to S and a path from B to S.

Return A → ...-> S → ...-> B.