## Hi5 Interview Question for Software Engineer / Developers

Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

Comment hidden because of low score. Click to expand.
0

One of the solution is to run BFS but it won't be very efficient. 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.

Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

Hi Gaurav,

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

Comment hidden because of low score. Click to expand.
0

This question was on a phone interview.

Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

Comment hidden because of low score. Click to expand.
0
of 0 vote

@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)

Comment hidden because of low score. Click to expand.
0
of 0 vote

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

Comment hidden because of low score. Click to expand.
0
of 0 vote

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 :

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.

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.