CareerCup

1. Assuming every person has id, sort friends of A and B O(NlogN)
2. Make sure A and B are not first degree friends. Binary search B in A's friends or vice versa. Return false if found.
3. For every friend in A, do binary search on B's friends O(NlogN). Return true if found, false otherwise.

One of the solution is to run BFS but it won't be very efficieint. One of the good way to solve this is to look the problem this way. Make a list of friends of A and make another list of friends of C. A and C are 2 degree friends if the two list we have made have at least one friend in common. This intersection can be efficiently done using O(n) time and memory complexity using a hash table.

this be done simply like this ...

bool friend_finder(friend *A, friend *C)
{
int found=0;
for(int i=0;i<a->total_friends;i++)
{
if(a->(friends+i)->friend==C)
{
found=1;
break;
}
}
if(found==0)
return false;
else
return true;
}

Hi Gaurav,

Can u please tell me are these questions asked on a phone interview or onsite interview?

borrow some idea from gauravk.18.

Create hash map for every person with person as the key, and the list of all his friend as the value. Then, ecah pair of people in the list is a two degree friends.

create hash map for every person with the person as the key, and the list of his friends as the value. Then when we got two person A and C, just merge the friends list of A and friends list of C, and if there are duplicate one, then, A and C is two degree friend.

@usafzz

if(a->(friends+i)->friend==C)
//this will not work as u go thro all the freinds of (friends+i), as it maynot have only one freind

so its a O(n^2)

with adjacency matrix O(n^2) space as preprocessing, we can check for 2 degree friend in O(n)

This can be done in O(1) time after doing a preprocessing using O(n2) space and O(n3) time . suppose Adj is the adjacency matrix of the above graph . So Adj[i][j] is "1" if and only if node "i" and "j" are directly connected .

Now , nodes "k" and "m" are two degree friends if the following condition is true :

if ((adj[k][0] && adj[0][m] ) || (adj[k][1] && adj[1][m] ) ..........|| (adj[k][MAXNODES -1 ] && adj[MAXNODES - 1][m] ) is true .

Consider another 2d array adj2[i][j] which stores the value of above condition for adj[i][j] . adj2 can be calculated as the 'boolean matrix product' of adj with itself . Here 'boolean matrix product' means normal matrix multiplication with "multiplication" operation replaced with "&&" and "plus" operation replaced with "||" operation .

Once adj2 is calculated we can say that "i" and "j" are 2 degree friends if and only if adj2[i][j] is 1.