Coding

Number of operations to make network connected

Asked at

Visa

1Give yourself 5 minutes

2Answer out loud, not in your head

3Then compare with the answer below

The problem

Given a graph with n vertices and m edges. The graph is represented by an array Edges, where Edge[i] = [a, b] indicates an edge between vertices a and b. One edge can be removed from anywhere and added between any two vertices in one operation. Find the minimum number of operations that will be required to make the graph connected. If it is not possible to make the graph connected, return -1.

**Input : **n = 4, Edge =[ [0, 1], [ 0, 2], [1, 2]]

Output: 1 Explanation: We need a minimum of 1 operation to make the two components connected. We can remove the edge (1,2) and add the edge between node 2 and node 3 like the following:

Input: n = 9, Edge = [[0,1],[0,2],[0,3],[1,2],[2,3],[4,5],[5,6],[7,8]]

**Output: **2 Explanation: We need a minimum of 2 operations to make the two components connected. We can remove the edge (0,2) and add the edge between node 3 and node 4 and we can remove the edge (0,3) and add it between nodes 6 and 8 like the following:

Input: n = 4, Edge =[[0, 1]]

1 <= n <= 104
1 <= Edge.length <= 104
Edge[i].length == 2

cpp

class Solution{
public:
    int solve(int n, vector<vector<int>> &Edge){
        
    }
};

java

class Solution {
    public int solve(int n, int[][] Edge) {
      
    }
}

python

class Solution:
    def solve(self, n, Edge):

javascript

class Solution {
    solve(n, Edge) {
        
    }
}

csharp

public class Solution {
    public int solve(int n, List<int[]> Edge) {
        
    }
}

func solve(n int, edges [][]int) int {

}

Stuck? Show a way to structure it+

01Check the necessary cable count first
02Union endpoints and ignore edges already in one component
03Count distinct roots after all unions
04Return components minus one

Reference answer

Start by restating the input contract for Number of operations to make network connected and testing the smallest boundary case before choosing the algorithm. If there are fewer than n-1 cables, connecting n computers is impossible. Otherwise use union-find to count connected components; each operation can use one redundant cable to join two components, so the answer is components minus one. Explain the invariant while coding, then show how each update preserves it. Union-find processes the graph in O((V + E) * alpha(V)) time and O(V) space, where alpha is the inverse Ackermann function. Walk through one nontrivial example aloud so the interviewer can see why the method reaches the intended result. Finally, call out input assumptions and failure cases rather than silently relying on them. A clean implementation should keep state local, use descriptive names, and avoid work that the invariant makes unnecessary.

Then expect these follow-ups

Why is n-1 a necessary threshold?
Tests: correctness reasoning
How would you return the actual rewiring operations?
Tests: implementation extension

Hiring now

Visa has 638 open roles right now

landed applies to roles like these for you, on each company’s own site, with answers written for the role.

Get 5x interviews10 free auto-applies. No card.

Senior Director, Greater China Tax
CN - Beijing, China
Sr. Manager, Government Sales Executive
IT - Rome, Italy
Director, Solution Architect, Global Growth Initiatives
GB - London, United Kingdom

Or practice this question first

Next question