Amazon Interview Question Software Engineer / Developers

  • amazon-interview-questions
    0
    of 0 votes
    15
    Answers

    Consider any social networking website like facebook etc.
    Design an algorithm / function that calculates minimum degree of connection between given two users. Assume that you are have already written function that returns a list of friends of given user :

    getFriends(username/id)

    [EDIT]
    Sorry guys for the wrong choice of words and caused confusion. It is "minimum degree of separation" and not connection.
    (I still think there isn't much different but quite sure it has already confused so many people...anyways... :) )

    follow this link for explanation : http://en.wikipedia.org/wiki/Six_degrees_of_separation

    - bobbysanders007 on July 01, 2012 in United States Report Duplicate | Flag
    Amazon Software Engineer / Developer Algorithm

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 on 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 on 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 on 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 on July 02, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

corrrect

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


Add a Comment
Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

Books

is a comprehensive book walking you through 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