Microsoft Interview Question
Applications DevelopersCountry: United States
Interview Type: Phone Interview
You can try this:
1) Create a graph between two people and their friends. If two people know each other (they are present in contacts list) make a vertex.
2) Find the shortest path between person A and B. Number of nodes in the path is the separation degree.
1.first, we should make sure that A,B can be connected, that means there must be at least one path from A to B. we can use Union Find to check it(is root(A)==root(B)?).
2.second, if A,B are conntected, then use BFS to find the shortest path.
- hmm December 15, 2013