Amazon Interview Question Software Engineer / Developers
Country: India
@Raydena:
Thanks for your comment.
But the graph of facebook contains trillions of users...it would be not efficient to run BFS on whole graph.
Also, how a simple BFS can assure that no other shorter path exist after it ends.
See, every node has its connection and one of which is shortest one(either from person A/Afriends end or Person B/Bfriends end). Also, u have to prevent to go yourself in loops
I did not say to execute on the whole facebook universe graph. Just start from one person than construct your graph.
Why do you think Breadth first search won't find the shortest path? I am not talking about depth first search. This is a weightless non-directional graph.
Keeping track of visited nodes will prevent loops.
Of course after 2nd or 3rd level things will get out of control assuming everyone has avg of 200 friends.
This is so simple, that you shouldn't even need to ask the question.
No need for any ridiculous algorithms, or complicated ideas.
If you want to find the path between A and B, then start by getting the friends of A and B.
Check if any of those friends are the same.
Then get the friends of the friends. Some will have the same friends, so always check for names already in the list, and skip them.
Then check if any of the friends of the friends of A, are the same as the friends of the friends of B.
Repeat this until you get a common friend.
This WILL be the shortest path.
It's pointless to be discussing specific named algorithms. This is so simple and straight forward, and there is no faster or better way than the intuitive way I just mentioned.
And it's very important to start from both A and B at the same time. Just getting friends of friends of.... from A until you find B, takes many factors more friend checking.
Even with the way I described, the number of people to check quickly grows to millions, but there is no faster way.
You could try to be smart, and first only check people in a specific area/country, based on where the people are located.
There are various similarity measures like cosine or co-relation which can be used ... even a modified apriori algo can be used ... but this can be answered only by ppl with knowledge in data mining ... I cant think of any way this can be solved other than IDA ie, iterative deepening search.
What abt IDA* ?
Yes it's a basic question, take a hashmap, keep value as distance of the friend from the starting friend and key as the friend id, and keep on iterating over the hashmap and adding the current person's friends in the hashmap, until you find the required friend.
Are you kidding me?
Suppose we are finding a connection bw A and B
You will first add all the friends of A in the Map (say they are 200)
Entries in Map = 200
Now you will process the first entry, which might also have 200 friends
Size after processing first entry = 400
Similarly after processing second entry 400 + 200 = 600
After processing 200th entry
200*200 = 40000
Till, then you will process, 201th to 40000th entry
I hope I have made my point.
@Sushant: Yes, it requires a lot of storage and time. But how else would you do it? Unless there's a way you can cache results (discuss with interviewer), there's not really a way to know the shortest path between two nodes without looking at all the paths of at least that length.
@Sushant: Hmmm...actually, I take that back. There are better ways of doing this, though not in a way that takes less than exponential time in the distance of the connection.
How about this: there is a path that is of length at most n between two vertices of a graph iff the intersection of the set of all nodes within distance n/2 of the first endpoint and the set of all nodes within distance n/2 of the second endpoint is nonempty. We can thus get one of these sets as a hashset and then do a set lookup on each of the elements in the other set. This would give us d^(n/2) time, where n is the distance and d is the expansion factor (200 in your example). Better than d^n time!
So something small like a friend of a friend or a friend of a friend of a friend of a friend can be verified quite reasonably with my algo.
Hmm... is that fact about all graphs, can you please point me to its proof.
And yes, in my opinion the only way to go about it is by using some sort of parallel processing or clustering technique such as the Map Reduce framework.
@Sushant: Suppose there is a vertex "v" that is distance n/2 from both endpoints, e1 and e2. So, there is a path from e1 to e2, namely, e1 -> v -> e2 that has length bounded by n/2 + n/2 = n.
Very bad idea, to just keep going until you find the other person.
It will be MUCH more efficient to work your way out from both people at the same time, until you find a common friend.
That reduces the number of friends you have to check, by many many factors.
Hashmap is a good solution to the problem. BFS can be very expensive if we are dealing here with millions of nodes. Also keeping track can also be impractical if multiple users are searching.
dijkstra algo must work. weight of my friends always 1 from me. so we have weights which are always positive
I would try something different then already mentioned in the answers.
Start from both the person.First find direct friend of both the persons( depth 1) and find a intersection, it not there then find all there friends of friends for each person and then find a intersection and continue in that way.
This can be solved using Dijkstra's algorithm.
Explanation: Assume Facebook has a small set of people- A,B,C,D,E,F,G.
A is friends with B,C,E
B is friends with C,D (and A)
D is friends with E & G (and B)
Now construct a connected graph.
Suppose we now want to find shortest hop between A & G, we can use Dijkstra's algorithm. Cant we then extrapolate this to real facebook situation?
"Now construct a connected graph." You want to construct the Whole Facebook connection Graph? I do not think this is practical.
why is this a wrong assumption? and why can't someone create a connected graph for all facebook connections ? the problem does not ask you to architect the complete solution which may involve things from neural networks & AI & much more.. i will be happy to hear the arguments on why we cant extrapolate?
The question explicitly mentions Facebook, And it has More than 800 million active users. This algorithm requires 2 traversals. 1 to construct the graph (and duplicate the Facebook data), and the second pass to find the connections. This is definitely a solution that works, but why waste so many CPU cycles if you can do it in 1 traversal only.
The way a see it, the connected graph is already on the database (Facebook) and you are provided with an API to solve the problem, so duplicating the Database seems to me as a waste of resources.
The problem can take huge memory and processor time if BFS is used.
My Initial assumption is to create groups according to some criteria(based on 'related' status).
Then find a path between groups of the person A and person B.
Then establish a path between the two groups, then between the two persons.
Now we have a path of some length between A and B.
Now we may try BFS between them , just to reduce the length between A and B.
I think its confusing, but my point is to establish a path between A and B and then reduce it to the minimum possible length.
So, BFS right... solves the matter.
BFS is a linear time (O(V + E)) algo that effectively computes shortest distance of any node, from a given node of interest, in a weightless graph.
Facebook might be a monster network, but connections or paths from a user or node fade away after a certain distance, so one cannot conclude BFS is ineffective.
Infact algo's like Dijkstra's, etc will be less effective compared to BFS in *this* case.
It all depends on how the facebook organizes its users. If you look at one question in career book, it explains different approaches like Facebook maintaining different servers placing users from one country in one server, etc.
Never the less the facebook has to use the graph datastructure to connect different people. In my view the interviewer is interested in different possible ways where we can easily deduce the shortest distance like based on the groups both share we can go through the common friends in those groups or something like this.
Although i am not giving any solution but this is my approach towards the problem. Basically we have either DFS or BFS to travel graph so we should use either of them
-Create a hash table for visited node
-Start two thread and one start from A and other one from B, both share above visited hash table
- Perform dfs from A(using first thread) and B(using second thread) and put new node in visited table; -There wont be any cycle
If we find that a node already exists in visited table then we found the min distance...
We can have some upper limit after which we can return none
Breadth first search on a graph?
- Rayden November 28, 2011