Google Interview Question for Software Engineers


Country: United States
Interview Type: Phone Interview




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

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

- code.best85 September 10, 2020 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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++)
{


}


}



}

- Engineer1111 September 14, 2020 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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 .

- Dynamo September 29, 2020 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

- pradeep.ilango.i3.mobile October 02, 2020 | Flag Reply


Add a Comment
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.

Learn More

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.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More