Find degrees of connection in a LinkedIn graph
Company: Liftoff
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
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.
Quick Answer: This question evaluates understanding of graph traversal, reachability and shortest-path concepts along with the ability to manage performance constraints on large sparse graphs.
Return the shortest number of connection edges between two people, optionally with one shortest path.
Constraints
- 0 <= src,dst < n
Examples
Input: (5, [(0, 1), (1, 2), (0, 3), (3, 4)], 0, 2, False)
Expected Output: 2
Explanation: Two hops.
Input: (3, [], 1, 1, True)
Expected Output: (0, [1])
Explanation: Source equals destination.
Input: (4, [(0, 1)], 0, 3, False)
Expected Output: -1
Explanation: Unreachable.
Input: (4, [(0, 1), (1, 2), (0, 2)], 0, 2, True)
Expected Output: (1, [0, 2])
Explanation: Direct shortest path.
Hints
- BFS in an unweighted graph finds minimum degree distance.