Amazon Interview Question
Software Engineer / DevelopersCountry: UK
Interview Type: In-Person
A bidirectional BFS, maintaining the a hash table of explored nodes for each and the hops to get to that node. Whenever the frontier node of either BFS touches a node that is in the explored set of explored nodes for the other, the total hops is the sum of from each BFS to the connecting node.
Consider each person as one node, and start from your self, keep one queue, which will keep the list of friends of friends.
Q <= Priority Queue which store lowest hop person on top
Insert me into the Q with hop = 0;
While(Q is not empty)
Node current = take the top node from the queue.
Search Node in Hierarchy and figure out its Friends, (We may even store that in the queue, but this increase queue size in case of large system
Insert all its friend with hop one more then current.
If any of the friend is the required person, we store the algorithm and report the hop.
Complexity : Depends upon friends count and search efficiency in the hierarchy.
Wow. All these answers suck. Do you really believe they want you to implement a breadth first search each time someone of the million users visits a connection and see the "degree" of the connection? LOL. Disqualified.
The right approach must be somewhere around using Floyd-Warshal-Algorithm offline in a batch job and optimizing it a bit for sparse 2d-arrays with parallelization and reducing the maximum degree to something reasonable, like 3 or maybe 4, which will make Floyd-Warshal much faster than N^3 for all normal data sets.
Then you could go into the server setup to do this computation on a few hundred million profiles. You could argue to run it more often on "active" users and update inactive connections less frequently, etc..
YES, LinkedIn will very likely not use Floyd-Warshal because at that scale it is likely not efficient enough unless you have some sort of behemoth super computer... Still it is a good shot into an unknown problem domain (distributed graph theory) and offers you a good starting point for in-depth discussions.
Maintain LinkedIn Persons as GraphNode and a connection as an edge from one graph node to another.
- smarthbehl July 14, 2015Now Do a breadth first search and while enqueuing connection in queue store the level as well .. when you find the desired person you will know its level also
BASICALY BFS