Google Interview Question
Software EngineersCountry: United States
Interview Type: Phone Interview
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.
@tassecarriere Thanks for posting this ... so as fast I know the signature of the function they are looking for is something like below :
- code.best85 September 10, 2020