Microsoft Online Assessment: Network Partition Problem

Problem Statement Given a network of $n$ data centers (nodes) connected by weighted bidirectional links (edges), partition the network into at most $k$ connected components by removing specifi

Problem Statement Given a network of $n$ data centers (nodes) connected by weighted bidirectional links (edges), partition the network into at most $k$ connected components by removing specific links. The objective is to minimize the maximum latency (edge weight) remaining within any of the resulting components.

Example

Input Data: *

Nodes: 3 *

Edges: 3 *

Max Regions ($k$): 2 *

Edge List (Node, Node, Weight): * (1, 2, 4) * (2, 3, 5) * (3, 1, 3)

Network Diagram:

(3) 3 / \ 5 / \ (1) ———— (2) 4

Solution Strategy To achieve the optimal partition, edges with the highest weights should be candidates for removal until the graph is split into the desired number of regions. 1.

Identify High-Cost Edges: The network has edge weights of 3, 4, and 5. 2.

Partition: Remove the links with weights 5 and 4. * Remove (2, 3) with weight 5. * Remove (1, 2) with weight 4. 3.

Resulting Components: *

Region 1: Nodes {1, 3} connected by the edge with weight 3. *

Region 2: Node {2} (isolated). *

Total Regions: 2 (Satisfies $k=2$). ### Result The highest remaining edge weight within any region is the link between 1 and 3.

Output: 3