Google Interview Question
Software EngineersCountry: United States
Interview Type: Phone Interview
@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;
I would propose something like this
- pradeep.ilango.i3.mobile October 02, 20201. 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.