Katkat
Back

Find shortest relationship path using BFS

GoogleSoftware Engineer · Technical Screen
MediumSoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

This problem tests your ability to model a relationship network as a graph and implement Breadth-First Search (BFS) to find the shortest path length between two nodes.

Problem Statement

You are given a list of direct friendships in a social network. Each friendship is represented as a pair of integers [user1, user2], indicating that user1 and user2 are connected. This connection is bidirectional.

Your task is to write a function that finds the "degrees of separation" between two given users, start_user and end_user. The degrees of separation is defined as the minimum number of edges in the path between two users. If there is no path between the two users, return -1.

Function Signature

def find_shortest_path(friendships, start_user, end_user):
    pass

Input

  • friendships: A list of lists, where each inner list contains two integers representing a friendship.
  • start_user: An integer representing the starting user ID.
  • end_user: An integer representing the target user ID.

Constraints

  • Number of users (nodes) N is up to 100,000.
  • Number of friendships (edges) E is up to 500,000.
  • User IDs are non-negative integers.

Examples

Example 1: Input: friendships = [[1, 2], [2, 3], [3, 4]], start = 1, end = 4 Output: 3 Explanation: The path is 1-2, 2-3, 3-4. Total of 3 edges.

Example 2: Input: friendships = [[1, 2], [3, 4]], start = 1, end = 4 Output: -1 Explanation: 1 and 4 are in disconnected components.

Edge Cases

  • The start user is the same as the end user (distance 0).
  • The graph is disconnected.
  • Users exist who have no friendships (not present in the input list).

Hints

Hint 1

Represent the network as an adjacency list to allow for efficient O(1) lookups of a user's neighbors.

Hint 2

Since the graph is unweighted, Breadth-First Search (BFS) is the optimal algorithm to find the shortest path distance in O(V + E) time.

Hint 3

Use a queue to track the frontier of nodes to visit and a dictionary or set to keep track of visited nodes to avoid cycles and redundant processing.

Follow-up questions

  • How would you modify your solution to return the actual path (the list of user IDs) rather than just the distance?
  • If the graph were extremely large and couldn't fit in memory, how would you approach finding the shortest path?
  • What changes would be necessary if the friendships were directed rather than bidirectional?