Coding questions · Liftoff

Find degrees of connection in a LinkedIn graph

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:

n people labeled 0..n-1
a list of undirected edges connections, where (a, b) means a and b are directly connected (1st-degree)

Given two people src and dst, return the minimum number of connections (degrees) needed to reach dst from src:

return 0 if src == dst
return 1 if directly connected
return 2 if connected via one intermediate person, etc.
return -1 if dst is not reachable from src

Optionally (if asked), also return one shortest path.

Constraints: 1 ≤ n ≤ 1e5, 0 ≤ |connections| ≤ 2e5. The solution should be efficient.

Degrees of Connection in an Undirected Graph

Return the shortest number of connection edges between two people, optionally with one shortest path.

Constraints

0 <= src,dst < n

Examples

Example 1

Input: (5, [(0, 1), (1, 2), (0, 3), (3, 4)], 0, 2, False)
Output: 2

Explanation: Two hops.

Example 2

Input: (3, [], 1, 1, True)
Output: (0, [1])

Explanation: Source equals destination.

Hints

BFS in an unweighted graph finds minimum degree distance.