CareerCup

Maintain LinkedIn Persons as GraphNode and a connection as an edge from one graph node to another.
Now 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

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.

A bidirectional breadth first search will be more optimal optimal

To find the shortest amount of hoops you could implement Dijkstra's Algorithm.

A* algorithm search for finding path from a start node(you) to a goal(another person) node in the smallest cost.

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.