DSA interview question

Find the MST Weight (Kruskal's Algorithm)

Hard · Data structures · Topics: graph, mst, kruskal, prim

The problem

An electricity board must connect V substations with power lines at minimum total cost, given the cost of each possible line. Kruskal's algorithm sorts all candidate lines from cheapest to most expensive and adds each one unless it would close a loop, checking with a disjoint set union. When V − 1 lines have been added, the network is a minimum spanning tree.

Example: 4 substations, lines 0-1 (10), 0-2 (6), 0-3 (5), 1-3 (15), 2-3 (4) → 19.

Function signature

long long kruskalMST(int V, vector<array<int, 3>> edges);  // connected, undirected

Test cases

Input `(V, edges)`	Output	Explanation
`(4, [[0,1,10],[0,2,6],[0,3,5],[1,3,15],[2,3,4]])`	`19`	4 + 5 + 10; 0-2 (6) would close a loop
`(3, [[0,1,1],[1,2,1],[0,2,1]])`	`2`	Any two of the three
`(2, [[0,1,7],[0,1,3]])`	`3`	Parallel lines: take the cheaper one
`(5, [[0,1,1],[1,2,1],[2,3,1],[3,4,1],[0,4,100]])`	`4`	The expensive line isn't needed
`(1, [])`	`0`

(Confirm: the graph is connected; weights are non-negative; parallel edges are allowed.)

How interviewers phrase it

"Find the total weight of the minimum spanning tree of a connected, undirected, weighted graph" (GeeksforGeeks "Minimum Spanning Tree"), using Kruskal's algorithm.

Clarifying questions to ask

Is the graph connected? (Yes. Otherwise Kruskal returns a minimum spanning forest.)
Edge list or adjacency list? (An edge list suits Kruskal.)
Do I need the edges themselves? (Collect them as they're accepted.)

Follow-ups to expect

"Why process edges in increasing weight?"
"Why skip edges inside one component?"
"Why DSU?"
"Can you stop early?"
"Complexity?"

Practise questions like this with a real engineer

On Practick another engineer interviews you live for 60 minutes on a question from this bank. They have the full interviewer guide beside the call: the expected answer to every follow-up, hints to give if you stall, and a scoring rubric. You get the model solution once the session settles. It is free: interview someone for an hour and you have earned your own.

Book a free mock interview