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 hard difficulty Coding & Algorithms question, commonly asked during Technical Screen rounds at Intuit.

What role is this question designed for?

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

Find Business Degrees of Separation | Intuit Coding Question

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.

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

Expected Output: (['B'], 0)

Explanation: When source and target are the same, the shortest path is just that single business, with degree 0.

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

Expected Output: ([], -1)

Explanation: A and D are in different disconnected components, so no path exists.

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

Expected Output: (['A', 'B', 'C', 'D', 'E'], 3)

Explanation: Duplicate edges do not change the answer. The shortest path is A -> B -> C -> D -> E, which has three intermediate businesses: B, C, and D.

Input: ([], 'X', 'Y')

Expected Output: ([], -1)

Explanation: With no relationships and different source/target businesses, there is no path.

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.

Quick Overview

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.