Katkat

Find degrees of connection in a LinkedIn graph

LiftoffSoftware Engineer · Onsite

Last 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:

  • 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.