Amazon Interview Question
Software Engineer / DevelopersCountry: United States
Interview Type: In-Person
when the distances are same. which you are taking to be one. then bfs does the same thing.
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.
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.
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)
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|
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.
- eugene.yarovoi July 13, 2012Think 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.