Number of Operations to Make Network Connected (Union-Find)
Given $n$ computers and connections, find the minimum number of cable moves required to make all computers connected. Model as a graph and use Union-Find.
Why Interviewers Ask This
Salesforce interviewers ask this to evaluate a candidate's ability to model real-world connectivity problems using Disjoint Set Union (DSU) data structures. They specifically test whether you can identify that redundant edges are the key resource for connecting isolated components, rather than just counting total connections.
How to Answer This Question
1. Clarify Constraints: Immediately state that if cables < n-1, return -1 since a connected graph requires at least n-1 edges. 2. Model as Graph: Explain that computers are nodes and cables are edges; the goal is to merge disconnected components into one set. 3. Choose Algorithm: Propose Union-Find with path compression and union by rank for near-linear time complexity O(E α(n)), which Salesforce values for efficiency. 4. Count Components: Iterate through all connections, performing unions. Track the number of disjoint sets remaining after processing all edges. 5. Calculate Moves: Derive the answer as (number of components - 1). This equals the minimum extra cables needed to bridge the gaps between isolated groups.
Key Points to Cover
- Identifying the lower bound requirement of n-1 edges before starting logic
- Correctly applying Union-Find with path compression for performance
- Recognizing that redundant edges provide the 'moves' needed
- Deriving the formula (components - 1) as the final answer
- Demonstrating O(E α(n)) time complexity awareness
Sample Answer
To solve this, I first check the fundamental constraint: we need at least n-1 cables to connect n computers. If the input has fewer cables than this threshold, it is impossible to connect everyone, so I would immediately…
Common Mistakes to Avoid
- Failing to handle the edge case where total cables are less than n-1
- Using BFS or DFS instead of Union-Find, leading to unnecessary code complexity
- Counting total edges rather than counting distinct connected components
- Ignoring the fact that moving a cable implies removing a redundant edge from a cycle
Sound confident on this question in 5 minutes
Answer once and get a 30-second AI critique of your structure, content, and delivery. First attempt is free — no signup needed.