FastPrepMinimize Malware Spread by Removing a Node

Minimize Malware Spread by Removing a Node

Visa logoVisa● MediumNEW GRADINTERNOA
Learn

Problem statement

There are gNodes servers numbered from 1 through gNodes. The parallel arrays gFrom and gTo describe bidirectional connections: edge i joins gFrom[i] and gTo[i].

The binary array malware describes the initial infection state. Server i is initially infected exactly when malware[i - 1] == 1. An infected server repeatedly infects every directly connected non-infected server until no additional infection is possible.

Before propagation begins, remove exactly one server, whether infected or not, together with all of its incident connections. Return the label of the server whose removal minimizes the number of infected servers remaining after propagation. If several removals produce the same minimum, return the smallest server label.

Function

minimizeMalwareSpread(gNodes: int, gFrom: int[], gTo: int[], malware: int[]) → int

Examples

Example 1

gNodes = 9gFrom = [1,2,4,6,7]gTo = [2,3,5,7,8]malware = [0,0,1,0,1,0,0,0,0]return = 3

Removing infected server 3 protects servers 1 and 2. Only servers 4 and 5 become infected, which is fewer than for any other removal.

Example 2

gNodes = 6gFrom = [1,1,1,1,1]gTo = [2,3,4,5,6]malware = [0,1,1,0,0,0]return = 1

Removing the uninfected center server 1 separates the two infected leaves from every other leaf, leaving only servers 2 and 3 infected.

Constraints

  • 1 ≤ gNodes ≤ 500
  • 0 ≤ gFrom.length = gTo.length ≤ 5000
  • Every edge endpoint is between 1 and gNodes.
  • malware.length = gNodes.
  • Every value in malware is 0 or 1, and at least one server is initially infected.

More Visa problems

See Visa hiring insights
public int minimizeMalwareSpread(int gNodes, int[] gFrom, int[] gTo, int[] malware) {
  // Write your code here.
}
gNodes9
gFrom[1,2,4,6,7]
gTo[2,3,5,7,8]
malware[0,0,1,0,1,0,0,0,0]
expected3
Checking account…