## Problem You are given `n` nodes and a list of potential edges, each with a cost. Find the minimum total cost to connect all nodes (i.e., build a minimum spanning tree). If it is impossible to connect all nodes, return -1. ```python from typing import List def min_connection_cost(n: int, edges: List[List[int]]) -> int: # n: number of nodes (1-indexed) # edges: [[node_a, node_b, cost], ...] # return: minimum total cost, or -1 if not fully connectable pass ``` **Example:** ``` n = 4 edges = [[1,2,3],[1,3,1],[2,3,2],[2,4,4],[3,4,1]] MST edges: (1,3,1), (3,4,1), (1,2,3) or (2,3,2) Minimum cost = 1+1+2 = 4 Output: 4 ``` ## Approach Kruskal's with Union-Find: sort edges by cost, greedily add edges that don't form a cycle. Time: O(E log E). ## Follow-ups 1. When would you prefer Prim's algorithm over Kruskal's? 2. What if some nodes already have a free connection (cost = 0) — does the algorithm change? 3. How would you find the second-minimum spanning tree? 4. In a distributed setting with millions of edges, how would you compute MST across partitioned data?

InterviewDB Question

Efficient Cost: Minimize Total Cost to Connect All Nodes in a Network

Question Details

Problem You are given n nodes and a list of potential edges, each with a cost. Find the minimum total cost to connect all nodes (i.e., build a minimum spanning tree). If it is impossible to connect all nodes, return -1. Example: Approach Kruskal's with Union-Find: sort edges by cost, greedily add edges that don't form a cycle. Time: O(E log E). Follow-ups When would you prefer Prim's algorithm over Kruskal's? What if some nodes already have a free connection (cost = 0) — does the algorithm chang…

Full Details

🔒

Unlock all Snowflake questions

Full insider details, leaked discussions, and candidate experiences.

or every company, $100/year →

About This Question

This is a reported interview question from a snowflake interview during the oa round.

It covers the following topics: System Design, Coding, Union Find, Oa .

Topics

System Design Coding Union Find Oa

Efficient Cost: Minimize Total Cost to Connect All Nodes in a Network

Question Details

Full Details

About This Question

Topics

More Snowflake Interview Questions