Problem Brief

Get Node To Remove

FULLTIMEOA

See Salesforce online assessment and hiring insights

Implement a prototype service for malware spread control in a network.

There are g_nodes servers in a network and g_edges connections between its nodes. The i^th bidirectional connection connects g_from[i] and g_to[i]. Some of the nodes are infected with malware. They are listed in the array malware, where if malware[i] = 1 node is infected, and if malware[i] = 0, node is not infected.

Any infected node infects other non-infected nodes, which are directly connected. This process goes on until no new infected nodes are possible. Exactly 1 node can be removed from the network. Return the index of the node to remove such that the total infected nodes in the remaining network are minimized. If multiple nodes lead to the same minimum result, then return the one with the lowest index.

Function Description

Complete the function getNodeToRemove in the editor.

getNodeToRemove has the following parameter(s):

1. int g_nodes: the number of nodes
2. int g_from[]: one end of the connections
3. int g_to[]: another end of the connections
4. int malware[]: the affected nodes

Returns

int: the optimal node to remove

1Example 1

Input

g_nodes = 9, g_from = [1, 2, 4, 6, 7], g_to = [2, 3, 5, 7, 8], malware = [0, 0, 1, 0, 1, 0, 0, 0, 0]

Output

Explanation

Initially, nodes [3, 5] are infected. At the end, nodes [2, 3, 4, 5] will be infected. If node 3 is removed, only nodes 4 and 5 are infected, which is the minimum possible. Return 3, the node to remove.

2Example 2

Input

g_nodes = 5, g_from = [1, 2, 3, 4], g_to = [2, 3, 4, 5], malware = [1, 1, 1, 1, 1]

Output

Explanation

Constraints

Limits and guarantees your solution can rely on.

1 ≤ g_nodes ≤ 10^3
0 ≤ g_edges ≤ min(g_nodes*(g_nodes-1)/2, 10^3)
1 ≤ g_from[i], g_to[i] ≤ n
malware[i] = 0 or 1.