## Amazon Interview Question for Software Engineer / Developers

Country: United States
Interview Type: In-Person

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

You should BFS search from both endpoints and do set intersection after each new level is visited. That way, if A and B are separated by distance d, after d/2 levels of friends have been searched from each, the intersection will be found. Set intersection of two sets of size m and n can be done in expected O(m + n), so if x is the approximate number of friends per person, this will run in roughly O(x^(d/2) + x^(d/2)) = O(x^(d/2)) instead of the O(x^d) we'd get from a BFS from only one of the endpoints. Searching from two endpoints has the square root of the runtime of the regular BFS algorithm.

Think about it this way. If you wanted to find whether two people share a mutual friend, would you 1) do a set intersection on the two people's sets of friends or 2) find all of A's friends, find all the friends of each such friend, and check whether B is in this giant set? The above algorithm is just a generalization of the insight that choice 1 is much better.

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

how can choice1 be a generalization of bidirectional bfs

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

@jitten: bidirectional bfs is a generalization of choice 1. Choice 1 is a special case of bidirectional bfs (when the distance is limited to a maximum of 2).

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

Shortest Path Algorithm where each edge is of weight one

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

corrrect

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

when the distances are same. which you are taking to be one. then bfs does the same thing.

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

I meant that shortest path helps us identify the shortest distance in case our nodes are variable distance apart. In this case all our nodes are one distance apart. then running a bfs would give all neighbors of a node and during recursion we can give a break statement on the time we find the node. that way we dont need to traverse through the whole bfs or shortest path algorithm. If we apply shortest path algorithm we are resting every node weather we have found the node or not. if we have found the node then there is no point going on with the search as it would not reduce the distance. it can only give equal or a greater distance.

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

What i see it as .. If you are my friend then you are one distance apart. if you are not my friend and my friends friend then you are 2 distance apart. so first i find you in all my friends. thats first thing. then i keep all my friends in queue if i dont find you then i dequeue every one.. one by one and search in there friends and put them in queue if i find you any where in my friends friends then your distance is 2 else it will increase. to keep track of the the distance, each node we are adding to the queue can be given a depth val of node as parent + 1 and setting my depth val as 0.

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

I think we can use an algorithm similar to the BFS algorithm.

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

Design an algorithm / function that calculates minimum degree of connection between given two users. - can u explain more about this sentence ...

Comment hidden because of low score. Click to expand.
-1
of 1 vote

what do you mean by minimum degree of connection ???

Comment hidden because of low score. Click to expand.
-1
of 1 vote

Assuming we need find the common friends, first, add all the friends(unique Ids) of person A to a hash table. Now, add the friends of Person B to the same hash table checking for collisions. The mutual friends will have same Id, hence same hash so there will be a collision. The complexity is O(m+n)

Comment hidden because of low score. Click to expand.
-1
of 1 vote

applying bfs and implementing a thread which returns true if user in list. and creating a thread hierarchy where one thread initiates thread* no of friends.

Comment hidden because of low score. Click to expand.
-2
of 2 vote

we can make find the total number of friends of each user and take an array of maximum*2 and mark M[i][j] =1 if a user is friend to a particular person or else 0. then we can use the Jaccard similarity coefficient to find the similarity between users which is J is equal to |A intersection B| / |A Union B|

Comment hidden because of low score. Click to expand.
-2
of 2 vote

if i understood the question correctly, we have to find the list of common friends.
this problem is exactly the same as, finding common elements in two arrays or list

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.

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