educative.io

Clarifying the problem for Minimize Malware Spread

Courses
,
#1

Return a node from initial such that, when this node is removed from the graph, M is minimized.

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.

Which of these should we return?

  1. a node from initial such that, when this node is removed from the graph, M is minimized.
    1. in this case, is the second quote inaccurate because we’re removing the node from the graph and it can’t be infected?
  2. a node from initial such that, when this node is removed from initial, M is minimized.
    1. in this case, is the first quote inaccurate because we’re removing the node from initial and not from the graph?

Example

graph: 1 - 2 - 3 - 4
initial: [1, 2]

  1. If we’re removing a node from the graph: removing 1 yields M = 3, and removing 2 yields M = 1, so return 2.
  2. If we’re removing a node from initial: removing 1 yields M = 4, and removing 2 yields M = 4, so return 1 because it’s the earlier index.

Course: Grokking Coding Interview Patterns in Python - AI-Powered Learning for Developers
Lesson: Minimize Malware Spread - Grokking Coding Interview Patterns in Python