Find degrees of connection in a LinkedIn graph
LiftoffSoftware Engineer · OnsiteLast updated
This question evaluates understanding of graph traversal, reachability and shortest-path concepts along with the ability to manage performance constraints on large sparse graphs.
You are given an undirected graph representing professional connections:
npeople labeled0..n-1- a list of undirected edges
connections, where(a, b)meansaandbare directly connected (1st-degree)
Given two people src and dst, return the minimum number of connections (degrees) needed to reach dst from src:
- return
0ifsrc == dst - return
1if directly connected - return
2if connected via one intermediate person, etc. - return
-1ifdstis not reachable fromsrc
Optionally (if asked), also return one shortest path.
Constraints: 1 ≤ n ≤ 1e5, 0 ≤ |connections| ≤ 2e5. The solution should be efficient.
Solution walkthrough is for members
Get the full walkthrough with reference code and complexity analysis, plus Kitty Coach at 300 messages a day. Hints, the code runner and community answers stay free.