Find Business Degrees of Separation
Company: Intuit
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: hard
Interview Round: Technical Screen
Implement a feature for a small-business network.
QuickBooks has data showing business relationships, such as one business regularly buying goods or services from another. Treat each relationship as an undirected connection between two businesses.
Given:
- A collection of business-to-business relationships, where each relationship connects two business IDs or names.
- A source business.
- A target business.
Return the shortest relationship path between the source and target if one exists, along with the degree of separation.
For this problem, define the degree of separation as the number of intermediate businesses on the shortest path. Therefore, if the shortest path is `A -> B -> C`, then `A` and `C` have degree of separation `1`.
Example:
Relationships:
```text
A <-> B
B <-> C
```
Query:
```text
source = A
target = C
```
Expected result:
```text
path = [A, B, C]
degree = 1
```
If multiple shortest paths exist, returning any one of them is acceptable unless otherwise specified. If no path exists, return an appropriate empty result such as `null`, an empty path, or degree `-1`, depending on the function contract you define.
Quick Answer: This question evaluates understanding of graph traversal and shortest-path computation, including modeling business relationships as undirected graphs and interpreting degrees of separation on the shortest path.
Implement a feature for a small-business network. Each business relationship connects two businesses and should be treated as an undirected edge in a graph. Given a collection of relationships, a source business, and a target business, return the shortest relationship path between the source and target. Also return the degree of separation, defined as the number of intermediate businesses on that shortest path. For example, the path ['A', 'B', 'C'] has degree 1 because only 'B' is between the endpoints. Return a tuple (path, degree), where path is the list of businesses in order. If source and target are the same, return ([source], 0). If no path exists, return ([], -1). If multiple shortest paths exist, returning any one of them is acceptable.
Constraints
- 0 <= len(relationships) <= 200000
- Each relationship contains exactly two business identifiers
- Business identifiers can be strings or integers and are compared by equality
- Duplicate relationships may appear and should not affect correctness
Examples
Input: ([('A', 'B'), ('B', 'C')], 'A', 'C')
Expected Output: (['A', 'B', 'C'], 1)
Explanation: The shortest path from A to C is A -> B -> C. The only intermediate business is B, so the degree is 1.
Input: ([('Shop1', 'Shop2'), ('Shop2', 'Shop3'), ('Shop3', 'Shop4')], 'Shop2', 'Shop3')
Expected Output: (['Shop2', 'Shop3'], 0)
Explanation: Shop2 and Shop3 are directly connected, so the shortest path has no intermediate businesses.
Hints
- Model the businesses as an unweighted graph. What graph traversal finds the shortest path in an unweighted graph?
- Store the parent of each visited business during traversal so you can reconstruct the path once you reach the target.