Microsoft Oa

Summary

I encountered a challenging graph problem involving network partitioning during my Microsoft Online Assessment.

Full Experience

During my Microsoft Online Assessment, I was presented with a complex problem concerning network partitioning. The task was to divide a network of data centers, connected by links with latencies, into a maximum of 'k' regions. The objective was to remove links such that the highest latency within any of the resulting regions was minimized.

Interview Questions (1)

Network Partition to Minimize Maximum Latency

Data Structures & AlgorithmsHard

You are given a network of data centers represented as nodes connected by bidirectional links (edges). Each link has a latency (weight).

You can remove some links to divide the network into at most k regions (connected components).

Your goal is to remove links such that the maximum latency (largest edge weight) within any region is as small as possible.

Example

Input

g_nodes = 3
g_edges = 3
k = 2

g_from = [1, 2, 3]
g_to = [2, 3, 1]
g_weight = [4, 5, 3]

Network Diagram

(3)
3 /   \ 5
/     

(1) ———— (2)
4

Explanation

The network has 3 data centers and 3 bidirectional links:
- 1 — 2 with latency 4
- 2 — 3 with latency 5
- 3 — 1 with latency 3

You need to split this into at most 2 regions (k = 2) by removing links to minimize the maximum latency inside any region.

Optimal Strategy

Remove the connections:

Between 1 and 2 (latency 4)
Between 2 and 3 (latency 5)

Now, regions are:

Region 1: (1, 3) with latency 3
Region 2: (2) alone

Maximum internal latency among all regions = 3