Quick Overview

This question evaluates understanding of graph traversal, reachability and shortest-path concepts along with the ability to manage performance constraints on large sparse graphs.

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.

Overview: 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.

Hints

  1. BFS in an unweighted graph finds minimum degree distance.

Degrees of Connection in an Undirected Graph

mediumLiftoffSoftware Engineer

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

View full question (all parts)

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.

Examples

Example 1
Input
(5, [(0, 1), (1, 2), (0, 3), (3, 4)], 0, 2, False)
Output
2
Notes
Two hops.
Example 2
Input
(3, [], 1, 1, True)
Output
(0, [1])
Notes
Source equals destination.

Constraints

  • •0 <= src,dst < n

Comments (0)

No comments yet. Be the first to comment!

Submit your answer

Approved first answer today earns 30 XP
Bold⌘BItalic⌘IInline code⌘`Bullet listTab to nest (○ ■)Numbered listTab to nest (a. i.)QuoteCode block
Formatting help
Signature
def solution(n: int, connections: list[tuple[int, int]], src: int, dst: int, return_path: bool = False) -> str:
Sample call
solution(5, [(0, 1), (1, 2), (0, 3), (3, 4)], 0, 2, False)
Language
Case 1
Input
(5, [(0, 1), (1, 2), (0, 3), (3, 4)], 0, 2, False)
Expected
2
Case 2
Input
(3, [], 1, 1, True)
Expected
(0, [1])

Browse More Questions