Day 19 of 30 days of Data Structures and Algorithms and System Design Simplified — Graphs
Welcome back peeps. Hope all’s well. In this post we will cover Graphs as follows —
What and Why Graphs(in 2–3 sentences)?
How does Graphs work?
Important Patterns and Techniques in Graphs Questions
Most Important Questions with Solutions
Tips and Techniques to solve Graphs Questions Fast.
Projects Videos —
All the projects, data structures, SQL, algorithms, system design, Data Science and ML , Data Analytics, Data Engineering, , Implemented Data Science and ML projects, Implemented Data Engineering Projects, Implemented Deep Learning Projects, Implemented Machine Learning Ops Projects, Implemented Time Series Analysis and Forecasting Projects, Implemented Applied Machine Learning Projects, Implemented Tensorflow and Keras Projects, Implemented PyTorch Projects, Implemented Scikit Learn Projects, Implemented Big Data Projects, Implemented Cloud Machine Learning Projects, Implemented Neural Networks Projects, Implemented OpenCV Projects,Complete ML Research Papers Summarized, Implemented Data Analytics projects, Implemented Data Visualization Projects, Implemented Data Mining Projects, Implemented Natural Leaning Processing Projects, MLOps and Deep Learning, Applied Machine Learning with Projects Series, PyTorch with Projects Series, Tensorflow and Keras with Projects Series, Scikit Learn Series with Projects, Time Series Analysis and Forecasting with Projects Series, ML System Design Case Studies Series videos will be published on our youtube channel ( just launched).
Subscribe today!
System Design Case Studies — In Depth
Design Instagram
Design Messenger App
Design Twitter
Design URL Shortener
Design Dropbox
Design Youtube
Design API Rate Limiter
Design Web Crawler
Design Facebook’s Newsfeed
Design Yelp
Design Uber
Design Tinder
Design Tiktok
Design Whatsapp
Most Popular System Design Questions
Mega Compilation : Solved System Design Case studies
Graphs
Importance : Very High
Note : New Graphs questions with solutions are added every day. So keep checking this post daily.
Let’s dive in!
What is Graphs?
Graph is a non linear data structure which consists of nodes connected by the edges ( which can undirected or directed).
Graphs are represented using —
1.Adjacency List — Used when the graph is sparse
2. Adjacency Matrix — Used when the graph is dense
Adjacency List
Every node in the graph has a list of its adjacent/neighboring nodes forming an adjacency list.
Adjacency Matrix
Adjacency Matrix — Matrix of size n*n where n is the no of edges is filled with 1’s or 0’s based on if there’s an edge is present from respective nodes.
Examples of Graphs problems —
Detect Cycle in graph
Topological sort
Shortest path in a graph (Weighted and Unweighted)
Minimum spanning tree etc
How does Graphs work?
A graph can be represented in different ways, such as an adjacency matrix or an adjacency list. An adjacency matrix is a two-dimensional array that represents the edges between the vertices, while an adjacency list is a list of linked lists that represents the edges between the vertices.
There are two ways you can traverse the graphs to search for a node in the graphs/subgraphs. Both the ways differ by the order in which nodes are traversed.
DFS — Stack is used
BFS — Queue is used
Depth First Search ( DFS)
Start the traversal from one node and subsequently do in depth traversal of the adjacent nodes by recursively calling the DFS function.
Breadth First Search ( BFS)
Start the traversal from one node and subsequently do level by level traversal of the adjacent/neighbor nodes.
Important Patterns and Techniques in Graphs Questions
Some important patterns and techniques in graph questions include:
- Graph traversal: This technique is used to traverse all the vertices of a graph and can be implemented using algorithms such as Breadth First Search (BFS) and Depth First Search (DFS).
- Shortest Path: This technique is used to find the shortest path between two vertices in a graph, using algorithms such as Dijkstra’s algorithm and Bellman-Ford algorithm.
- Minimum Spanning Tree: This technique is used to find the minimum spanning tree of a graph, using algorithms such as Kruskal’s algorithm and Prim’s algorithm.
- Strongly Connected Components: This technique is used to find the strongly connected components of a directed graph, using algorithms such as Tarjan’s algorithm and Kosaraju’s algorithm.
Most of the questions wrt graphs —
- Traversals
- Detect Cycle in the graph
- Island related questions
- Calculate area of island/square in the adjacency matrix
Most Important Questions with Solutions
Note : New Graphs questions with solutions are added every day. So keep checking this post daily.
Golden rule is — Learn by doing/implementing
In this we will see most important Graphs questions.
Clone Graph
Question —
Given a reference of a node in a connected undirected graph.
Return a deep copy (clone) of the graph.
Each node in the graph contains a value (int) and a list (List[Node]) of its neighbors.
class Node {
public int val;
public List<Node> neighbors;
}Example :
Input: adjList = [[2,4],[1,3],[2,4],[1,3]]
Output: [[2,4],[1,3],[2,4],[1,3]]Solution :
Main Logic/Idea —
The main logic is to create a copy of the nodes and then connect them same structurally by traversing through its neighbors in the adjacency list.
Implementation —
def cloneGraph(self, node: 'Node') -> 'Node':
hMap = {}
def cGraph(node):
if node in hMap:
return hMap[node]
copy = Node(node.val)
hMap[node] = copy
for neighbor in node.neighbors:
copy.neighbors.append(cGraph(neighbor))
return copy
return cGraph(node) if node else NoneQuestion Link
Similar Pattern —
Clone Binary Tree With Random Pointer
Full Code Video Explanation ( In progress. Subscribe today for updates) :
— — — — — — — — — — — — — — — — — — — — — — — — — — — — — — —
Longest Increasing Path in a Matrix
Question —
Example 1:
Input: s = "pwwkew"
Output: 3Solution :
Main Logic/Idea —
The main logic is to go through the matrix by performing recursive dfs ( in all the directions) and return the longest increasing path. Check for the boundary conditions at every step.
Implementation —
def longestIncreasingPath(self, matrix: List[List[int]]) -> int:
rows, cols, temp = len(matrix), len(matrix[0]),{}
def calcPath(r,c,previousVal):
ans = 1
if (r<0 or r == rows or c<0 or c==cols or matrix[r][c] <= previousVal):
return 0
if (r,c) in temp:
return temp[(r,c)]
ans = max(ans,1+calcPath(r+1,c,matrix[r][c]))
ans = max(ans,1+calcPath(r,c+1,matrix[r][c]))
ans = max(ans,1+calcPath(r-1,c,matrix[r][c]))
ans = max(ans,1+calcPath(r,c-1,matrix[r][c]))
temp[(r,c)] = ans
return ans
for ro in range(rows):
for co in range(cols):
calcPath(ro,co,-1)
return max(temp.values())Question Link
Similar Pattern —
Number of Increasing Paths in a Grid
Full Code Video Explanation ( In progress. Subscribe today for updates) :
Note : New Graphs questions with solutions are added every day. So keep checking this post daily.
Complexity Analysis
Before this section, read complexity analysis post.
Time complexity of BFS and DFS
Adjacency List — O(V + E)
Adjacency Matrix — O(V²)
Where E is the edges and V is the nodes.
Tips and Techniques to solve Graphs Questions Fast.
Before attempting the graph questions —
- Know how to implement DFS and BFS.
- Know how recursion works.
- Know how to create adjacency matrix and adjacency list.
That’s it for now. Day 20: Heap/Priority Queue coming soon !
Let me know if you have questions in the comment section below. Subscribe/ Follow, Like/Clap as it will encourage me to write more in my free time and Stay Tuned!!
Read More —
11 most important System Design Base Concepts
6. Networking, How Browsers work, Content Network Delivery ( CDN)
13. System Design Template — How to solve any System Design Question
Some of the other best Series —
30 days of Data Structures and Algorithms and System Design Simplified
Data Science and Machine Learning Research ( papers) Simplified **
100 days : Your Data Science and Machine Learning Degree Series with projects
Complete Data Visualization and Pre-processing Series with projects
Exceptional Github Repos — Part 1
Exceptional Github Repos — Part 2
Tech Newsletter —
If you are interested, you can join my newsletter through which I send tech interview tips, techniques, patterns, hacks — Software Development, ML, Data Science, Startups and Technology projects to more than 30K readers. You can subscribe to Tech Brew :
For Python Projects —
For complete 60 days of Data Science and ML : Day 1 — Day 60 : Quick Recap of 60 days of Data Science and ML
Follow for more updates. Stay tuned and keep coding!
For other projects, tune to —
Build Machine Learning Pipelines( With Code)
Recurrent Neural Network with Keras
Clustering Geolocation Data in Python using DBSCAN and K-Means
Facial Expression Recognition using Keras
Hyperparameter Tuning with Keras Tuner
Custom Layers in Keras
