FastPrep
Problem · Graph

Get Node To Remove

Learn this problem
● MediumSalesforceFULLTIMEOA
See Salesforce hiring insights

Problem statement

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 ith 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

getNodeToRemove(g_nodes: int, g_from: int[], g_to: int[], malware: int[]) → int

Complete the function getNodeToRemove in the editor.

getNodeToRemove has the following parameter(s):

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

Returns

int: the optimal node to remove

Examples

Example 1

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

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.

Example 2

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

Constraints

  • 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.

More Salesforce problems

drafts saved locally
public int getNodeToRemove(int g_nodes, int[] g_from, int[] g_to, int[] malware) {
  // write your code here
}
g_nodes9
g_from[1, 2, 4, 6, 7]
g_to[2, 3, 5, 7, 8]
malware[0, 0, 1, 0, 1, 0, 0, 0, 0]
expected3
checking account