FastPrep
Problem

Small Business Network: Degrees of Separation

IntuitPHONE SCREEN

QuickBooks stores business relationships between companies. Each relationship connects two businesses, and relationships should be treated as undirected graph edges.

Given the relationship list, a source business, and a target business, return one shortest relationship path from source to target. The path should include both endpoints.

If no relationship path exists, return an empty array. If source is the same as target, return an array containing only that business.

Examples
01 · Example 1
relationships = [["A", "B"], ["B", "C"]]
source = "A"
target = "C"
return = ["A", "B", "C"]

The relationships form A <--> B <--> C, so the shortest path from A to C goes through B.

02 · Example 2
relationships = [["A", "B"], ["C", "D"]]
source = "A"
target = "D"
return = []

A and D are in different connected components, so there is no relationship path.

Constraints
  • Each entry in relationships contains exactly two business names.
  • Relationship edges are undirected.
  • If multiple shortest paths exist, returning any one shortest path is acceptable.
More Intuit problems
drafts saved locally
public String[] shortestBusinessPath(String[][] relationships, String source, String target) {
  // write your code here
}
relationships[["A", "B"], ["B", "C"]]
source"A"
target"C"
expected["A", "B", "C"]
sign in to submit