How should I practice Minimize Malware Spread by Removing a Node?

Start by reading the full statement, solve the visible examples, then compare the pattern against related Akuna Capital online assessment problems in FastPrep.

Is Minimize Malware Spread by Removing a Node associated with Akuna Capital?

FastPrep tags this as a Akuna Capital online assessment coding practice problem when the problem catalog has that company and stage context.

Problem · Graph

Minimize Malware Spread by Removing a Node

Learn this problem

● Medium

Akuna CapitalINTERNOA

Problem statement

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

The binary array malware describes the initial infection state. Node i + 1 is initially infected exactly when malware[i] == 1.

Before malware spreads, remove exactly one initially infected node and all of its incident connections. Then every infected node repeatedly infects each directly connected non-infected node in the remaining network until no new node can be infected.

Return the label of the removed node that minimizes the total number of infected nodes remaining after propagation. If several removals produce the same minimum, return the smallest node 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

Nodes 3 and 5 are initially infected. Removing node 3 prevents infection in the component containing nodes 1 and 2, leaving only nodes 4 and 5 infected. Removing node 5 would leave three infected nodes, so the answer is 3.

Example 2

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

Removing either initially infected endpoint leaves two infected nodes after propagation. The tie is resolved in favor of the smaller node label, 1.

Constraints

1 <= gNodes <= 2000
gFrom.length == gTo.length
Every edge endpoint is between 1 and gNodes.
malware.length == gNodes
Every value in malware is 0 or 1, and at least one node is initially infected.