Learn essential coding patterns to answer problems and prepare for tech companies' interviews.

Ace the JavaScript Coding Interview

This module teaches us the underlying patterns behind common coding interview questions. By learning these essential patterns, we'll be able to unpack and answer any problem the right way—just by assessing the problem statement. This approach was created by FAANG hiring managers to help us prepare for the typical rounds of interviews at major tech companies like Apple, Google, Meta, Microsoft, and Amazon.

By the end of this module, we'll have the skills we need to unlock even the most challenging questions, grok the coding interview, and level up our career with confidence.

Coding Interview Patterns

# Statement
You’re given a network of $n$ nodes as an $n \times n$ adjacency matrix graph with the $i^{th}$ node directly connected to the $j^{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, $M$ 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, $M$ is minimized. If multiple nodes can be removed to minimize $M$, 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 \leq$ n $\leq 50$
* `graph[i][j]` is $0$ or $1$.
* `graph[i][j] == graph[j][i]`
* `graph[i][i] == 1`
* $1 \leq$ `initial.length` $\leq n$
* $0 \leq$ `initial[i]` $\leq n - 1$
* All the integers in the `initial` are unique.

# Solution
Since we have to check for infected nodes in each connected component, we need to find all the connected components in a graph. To do this, we use the `UnionFind` data structure that finds all of the graphs’s connected components. 

The steps of the algorithm are given below:
1) Find all of the graph’s connected components using the `UnionFind` data structure.

2) Traverse the `initial` array and store all the connected components with at least one infected node in a hash map, `infected`.

3) Traverse the `initial` array again and calculate the number of infections (from the `infected` hash map) in each connected component containing one or more infected nodes.
   - If a connected component contains more than one infected node, ignore it and move to the next iteration of the loop.
   - Otherwise, calculate the size of the connected component.

4) Find the connected component with the greatest size, containing only one initially infected node from step $3$.

5) If there are multiple components that are the same size that would count as the largest connected component, choose the component with the smallest index.

The slides below illustrate how we would like the algorithm to run:

Let's solve the Minimize Malware Spread problem using the Union Find pattern.

Solution: Minimize Malware Spread

Statement