Minimize Malware Spread
Hard · Graphs · about 30 minutes
Asked at Google, Amazon, Dropbox, Microsoft.
graph is an n × n adjacency matrix of a network; initial lists infected nodes. Malware spreads to every node connected to an infected node. Removing exactly one node from initial (it can still be infected through others) — return the node whose removal minimizes the final number of infected nodes, choosing the smallest index on a tie.