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 return -1. Assuming we have enough cables, the problem becomes finding how many disconnected components exist in the graph. I would use the Union-Find data structure because it efficiently manages merging sets of nodes. I initialize each computer as its own parent. As I iterate through the given connections, I attempt to union the two endpoints. If they are already in the same set, that cable is redundant; otherwise, I merge their sets. After processing all connections, the number of operations required is simply the number of disjoint sets minus one. For example, if we have 6 computers and 4 connections forming 3 separate islands, we need 2 additional moves to link them together. This approach runs in nearly constant time per operation, making it optimal for large-scale networks like those Salesforce manages.
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
Practice This Question with AI
Answer this question orally or via text and get instant AI-powered feedback on your response quality, structure, and delivery.
Related Interview Questions
Find K Closest Elements (Heaps)
Medium
MetaEvaluate Reverse Polish Notation (Stack)
Medium
SpotifyConvert Binary Tree to Doubly Linked List in Place
Hard
MicrosoftDesign a Set with $O(1)$ `insert`, `remove`, and `check`
Easy
CiscoTrade-offs: Customization vs. Standardization
Medium
SalesforceDesign a System for Monitoring Service Health
Medium
Salesforce