How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a medium difficulty Coding & Algorithms question, commonly asked during Technical Screen rounds at Google.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Google during technical interviews.

Find shortest relationship path using BFS

Company: Google

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

## Problem You are given a set of pairwise **relationships** between entities (people/services/etc.). Treat each relationship as an **undirected edge** in a graph. Given: - `relationships`: a list of pairs `[u, v]`, meaning `u` is related to `v`. - `start`: the starting entity. - `target`: the destination entity. ### Task 1. Build an adjacency structure (e.g., a hash map from node → neighbors). 2. Use **BFS** to find the **minimum number of relationship-hops** from `start` to `target`. ### Output Return the length of the shortest path in hops (number of edges). If `target` is unreachable, return `-1`. ### Follow-ups (discuss, no need to fully implement unless asked) - Return the actual path (list of nodes) instead of only its length. - Handle many queries (`start`, `target`) efficiently. - Consider directed relationships (only `u → v`). ### Constraints (reasonable assumptions) - `1 ≤ len(relationships) ≤ 2e5` - Node IDs are strings or integers. - Graph may be disconnected.

Quick Answer: This question evaluates proficiency in graph representations and traversal algorithms—specifically BFS and adjacency-structure construction—for computing unweighted shortest paths and reasoning about reachability.

You are given a list of pairwise relationships between entities. Treat each relationship as an undirected edge in a graph, where each entity is a node. Given `relationships`, `start`, and `target`, build an adjacency structure and use Breadth-First Search (BFS) to find the minimum number of relationship-hops needed to reach `target` from `start`. Return the number of edges in the shortest path. If `target` cannot be reached from `start`, return `-1`. If `start` and `target` are the same entity, return `0`.

Constraints

0 <= len(relationships) <= 200000
Each relationship contains exactly two node IDs
Node IDs are hashable values such as strings or integers
The graph may be disconnected
Duplicate relationships and self-loops may appear

Examples

Input: ([['A', 'B'], ['B', 'C'], ['C', 'D']], 'A', 'D')

Expected Output: 3

Explanation: The shortest path is A -> B -> C -> D, which uses 3 edges.

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

Expected Output: 2

Explanation: There are multiple paths, but the shortest is 1 -> 2 -> 5, which has 2 hops.

Input: ([['x', 'y'], ['a', 'b']], 'x', 'b')

Expected Output: -1

Explanation: The graph has two disconnected components, so b is unreachable from x.

Input: ([], 'solo', 'solo')

Expected Output: 0

Explanation: Start and target are the same, so the shortest path length is 0 even with no relationships.

Input: ([[1, 1], [1, 2], [1, 2], [2, 3]], 1, 3)

Expected Output: 2

Explanation: Self-loops and duplicate edges do not change the shortest path. The minimum path is 1 -> 2 -> 3.

Hints

Since every relationship-hop has the same cost, BFS is the right traversal to find the shortest path.
First build a dictionary that maps each node to its list of neighbors, then explore level by level from `start`.

Quick Overview

This question evaluates proficiency in graph representations and traversal algorithms—specifically BFS and adjacency-structure construction—for computing unweighted shortest paths and reasoning about reachability.