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.

- eugene.yarovoi July 13, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

how can choice1 be a generalization of bidirectional bfs

- jiten February 27, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- eugene.yarovoi February 27, 2013 | Flag
Comment hidden because of low score. Click to expand.
2
of 2 vote

Shortest Path Algorithm where each edge is of weight one

- Rashmi July 02, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

corrrect

- Sourabh July 05, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- ashish.singla87 July 23, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- ashish.singla87 July 23, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- ashish.singla87 July 23, 2012 | Flag
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.

- Pavan Dittakavi July 01, 2012 | Flag Reply
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 ...

- raunak July 01, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

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

- rohithindustani2004 July 02, 2012 | Flag Reply
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)

- Anonymous July 02, 2012 | Flag Reply
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.

- Ashish July 11, 2012 | Flag Reply
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|

- A. July 01, 2012 | Flag Reply
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

- ajaypathak July 02, 2012 | 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