Search⌘ K
AI Features
Home
Courses
Grokking the Coding Interview Patterns in Python

Minimize Malware Spread

Explore the Union Find technique to solve the minimize malware spread problem, where you identify and remove nodes to reduce infection in a connected network. Understand how to analyze graph connectivity and apply efficient algorithms to prevent widespread malware propagation.

We'll cover the following...

Statement

You’re given a network of nn nodes as an n×nn \times n adjacency matrix graph with the ithi^{th} node directly connected to the jthj^{th} node if graph[i][j] == 1.

A list of nodes, initial, is given, which contains nodes initially infected by malware. When two nodes are connected directly and at least one of them is infected by malware, both nodes will be infected by malware. This spread of malware will continue until every node in the connected component of nodes has been infected.

After the infection has stopped spreading, MM will represent the final number of nodes in the entire network that have been infected with malware.

Return a node from initial such that, when this node is removed from the graph, MM is minimized. If multiple nodes can be removed to minimize MM, return the node with the smallest index.

Note: If a node was removed from the initial list of infected nodes, it might still be infected later on due to the malware’s spread.

Constraints:

  • graph.length == graph[i].length
  • 2≤2 \leq n ≤50\leq 50
  • graph[i][j] is 00 or 11.
  • graph[i][j] == graph[j][i]
  • graph[i][i] == 1
  • 1≤1 \leq initial.length ≤n\leq n
  • 0≤0 \leq initial[i] ≤n−1\leq n - 1
  • All the integers in the initial are unique.

Examples

canvasAnimation-image
1 / 2

Understand the problem

Let’s take a moment to make sure you’ve correctly understood the problem. The quiz below helps you check if you’re solving the correct problem:

Minimize Malware Spread

1.

Given the following graph and the initially infected nodes, which node will help minimize the malware spread?

graph = [[1, 1, 1],
                [1, 1, 0],
                [1, 0, 1]]

initial = [1, 2]

A.

0

B.

1

C.

2

1 / 2

Figure it out!

We have a game for you to play. Rearrange the logical building blocks to develop a clearer understanding of how to solve this problem.

Sequence - Vertical
Drag and drop the cards to rearrange them in the correct sequence.
1
2
3
4
5

Try it yourself

Implement your solution in main.py in the following coding playground. You will need the provided supporting code to implement your solution.

Python
usercode > main.py
"""

⬅️ We have provided a union_find.py file under the "Files" tab 

of this widget. You can use this file to build your solution.

"""

from union_find import *





def min_malware_spread(graph, initial):



    # Replace this placeholder return statement with your code

    return 0
Minimize Malware Spread