CareerCup

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