CareerCup

I would propose something like this

1. AddFreindShip - Connect 2 nodes with an edge.
2. GetSuggestedFriends - do bfs from the node. All the nodes in the level 1 are node's friends. All nodes in 2nd level friends of friends. They are the target nodes. Among them, we have to see who has more number of edges from level 1 nodes. we can count that during bfs. Iterate the count list and return the nodes with the highest count.

@tassecarriere Thanks for posting this ... so as fast I know the signature of the function they are looking for is something like below :

AddFreindShip(Person a, Person b) : This will add connection between two in the network

List<Person> GetSuggestedFriends(Person a) : This will check with everyone and will return the list of people with most common friends... am i correct?

This would depend on the size of the array , but we can use bitwise operators to effectively do it.

Lets assume a couple of helper function:

int numberOfSetBits(unsigned long int a) returns the number of bits that are set to 1

if it is upto 64 people, we can use an unsigned long int in the form of an array

global int a[64];

void addFriend(int userId, int newFriendId)
{
a[userId] = a[userId] |= 1 << x;
}

List<int> GetSuggestedFriends(int UserId)
{
int friend_ctr;
int total_population
for(friend_ctr = 0; friend_ctr < total_population;friend_ctr++)
{


}


}



}

It's easiest to use a graph where each node is a person and each edge represents a friendship. Edges will be made by using a Map where the key will represent the node and the value will represent a list of neighboring nodes. Check each neighbor's neighbor (friend's friend), if one of the neighbor's neighbor has a neighbor that is in the user's friend list (other than the neighbor that connected the user with that neighbor's neighbor) then, if it is not already a friend, suggest that node as a friend .

I think the simplest way would be to use adjacency matrix.
-> Let's say there are 10 users right now in the network
-> Use a 10X10 matrix (M) where M[i][j]=1 means i and j are friends (Of-courseM[j][i] will also be 1 ). keep M[i][i]=0.
-> AddFreindShip(int i, int j): Just mark M[i][j]=1 and M[j][i]=1;
-> List<Integer> GetSuggestedFriends(int i): These could be friends of friends. Just retrieve all the integers in i row where value M[i][0 to 9] == 1. Let' s say you have got a List<Integer> tmp. Now find all friends of the person in tmp list. Make sure you are not adding duplicate values and also do not include the numbers which are already in tmp;