TLDR

1. Welcome!

2. Intelligent automation from ELEKS

3. Recommendations I live by!

4. Self-Gaslight of the week - Master your behavioral interview

5. Hacks of the week

6. JOBS & SCHOLARSHIPS

Day 1 : 1971 Find if Path exists

Given a bi-directional graph with n vertices and edges represented as a 2D array, determine if a valid path exists between a specified source and destination vertex. Return true if a path exists, otherwise return false.

Before we dive in,

Breathe. I used to hyperventilate every time I saw a graph problem.

By the time you finish reading this email, you’ll be able to do a graph problem in your sleep.

The first thing for any graph problem is to build an adjacency matrix.

An adjacency matrix is just another way to show the relationships between nodes.

Each row and column corresponds to a node, and the matrix's values show which nodes are connected.

Since the graph is bidirectional, we reflect the relationship by pushing each connected node to both corresponding rows in the adjacency matrix.

Now let’s build it:

for(auto x: edges){
   adj[ x[0] ].push_back( x[1] );
   adj[ x[1] ].push_back( x[0] );
  }

Once we’ve built our adjacency matrix, the magic happens. 🪄 

We will recursively go through the matrix from source to destination and find whether or not there is a path.

To ensure we only visit each node once, we are going to keep a boolean vector, where we keep track of a node that has been visited or not.

We’ll start by iterating through the nodes connected to our source.

For each neighbor, we’ll check if it has already been visited. If it hasn’t, we’ll dive deeper, exploring the neighbors of that neighbor.

Once we’ve gone through the whole matrix, we can confirm visited[destination] is true, it means a path exists!

Complete code:

#include <vector>

class Solution {
public:


void DFS(vector<vector<int>>& adj, int source, vector<bool>& visited){
        visited[source] = true; 
        for(int x=0; x<adj[source].size(); x++){
            if(!visited[adj[source][x]]){
                DFS(adj,adj[source][x],  visited);
            }
        }
    }
    
bool validPath(int n, vector<vector<int>>& edges, int source, int destination) {
        vector<vector<int>> adj(n); 
        vector<bool> visited(n, false);
        for(auto x: edges){
           adj[x[0]].push_back(x[1]);
           adj[x[1]].push_back(x[0]);
        }

        DFS(adj,source, visited);

        return visited[destination];
    }
};

Recommendations

Level up your inbox by subscribing to what I am subscribed to!

Self-gaslight of the week

I truly believe you can gaslight yourself to success.

1. Your 20’s suck and that is freeing

2. NVIDIA was started in a Denny’s

Hacks of the week

1. H + STAR + G method to behavioral interviews

2. Never reveal you are unemployed, it gives desperation.

Jobs and Scholarships

1. Scholarship list!

2. Software jobs list!