Graphs are a fundamental topic frequently covered in coding interviews at top companies. It's also a vast area that programmers must study extensively to excel in coding interviews. With over 5 subtopics such as Breadth First Search, Depth First Search, Topological Sorting, Minimum Spanning Tree, and Shortest Path Algorithms, the number of related problems is substantial! In this article, we will go over the common Patterns of graph problems asked in coding interviews along with sample problems that you should practice. There are over 500 problems for Graphs on Leet code! However, most of these problems can be solved with just Graph traversal algorithms and Topological sorting. Focus on these more! Pattern #1 - Problems Involving Shortest Path Algorithm in Unweighted Graphs Algorithms Used: Breadth First Search These are the problems where you need to directly or indirectly compute the shortest distance to the nodes. These could be via a single source or multiple sources. let us take a look at the . The key idea to solve this problem is to determine that the time at which each orange becomes rotten is equal to the shortest distance of that orange from its nearest rotten orange. This can be easily solved by using Breadth First Search and making sure that when we perform a breadth-first search, we add the coordinates of the rotten oranges in the queue. For example: Rotting Oranges Problem on Leetcode Pattern #2 - Problems Where We Start Graph Traversal from Cells on Boundaries These are the problems where we need to start the graph traversal from the boundaries of the cells, for ex take a look at the . In this problem, if you start BFS from every cell and try to see if you can reach either the Pacific or Atlantic Ocean, the solution’s time complexity would increase. This is because you would have to start the BFS O(MxN) Pacific Atlantic Problem times and each BFS can take up to O(MN) time as well.  So, overall complexity becomes O(M*N) ^2). So, instead of that, we do the BFS only starting from the boundary cells, therefore we reduce the complexity to O (M*N*(M + N)). Algorithms Used: Breadth First Search and Depth First Search 3. Pattern #3 - Problems Where We Model Input as a Graph and then use topological sorting to get the output. These are the problems where we need to first model the input given in the problem as a graph and then either detect there is a cycle or determine the order using topological sort and use this information. For example: In the problem on Leetcode we are given a new language where the lexicographic order of the letters is not known. However, we are given the list of some sample words in lexicographic order is given. Using that we need to determine the valid order of letters in this new “alien” language. For ex, if the input is ["wrt","wrf","er","ett","rftt"] then using it we can determine that the order of letters in this alien language is [“w”, “e”, “r”, “t”, “f”]. Alien Dictionary We can solve this problem first by modeling each letter as a node and then we determine which letter comes before which letter using consecutive words. For ex, if we compare “wrt” and “wrf” we can determine that “t” should come before “f”. So, we add an edge from “t” to “f”. Similarly, when we compare “wrf” to “er” we can determine that “w” should come before “e”. So, we add an edge from “w” to “e” in the graph. Like this we add all the edges and then topological sort the graph. Another example of this problem is where we model each course as a node. Course Schedule Topological Sorting and Cycle Detection Pattern #4 - Problems Involving Shortest Path Algorithm Over Weighted Graphs/Binary Weighted Graphs These are the problems that can directly be solved by applying the standard shortest path algorithm after modeling the input as a graph. For example, if we look at the problems on Leetcode, the time it takes for the signal to reach the farthest node is the distance of the farthest node from the source node. Network Delay Time Another example can be . In this problem, we model each number within the snakes and ladder board as a node and model each dice roll as an edge with weight 1 (as we need to throw the dice once to follow this edge). Each snake or ladder can be modeled as an edge with weight 0 (as we don’t need to throw the dice to go over the edge). Snakes & Ladder Problems on Leetcode Dijkstra’s algorithm and 0-1 BFS Pattern #5 - Problems Involving Minimum Spanning Tree These are the problems that can directly be by applying either Kruskal’s or Prim’s algorithm. For example, Points For ex, in this problem, we model each point as a graph and model the edges b/w each node with the weight as the Manhattan distance b/w the two points. Then we apply any of the minimum spanning tree algorithms directly. Min Cost to Connect All With these patterns, you should be equipped to tackle any Graph problem that comes your way in Coding Interviews! [Affiliate link] If you are interested in a deeper dive into other patterns and Leetcode Problems, you should definitely check my course on It’s available on Udemy and is one of the highest-rated courses on problem-solving. Mastering Leetcode in Java: Top 130 Most Asked Problems You would definitely enjoy it!

Walkthroughs, tutorials, guides, and tips. This story will teach you how to do something new or how to do something better.

Understanding Time Complexity Of Algorithms - Part 1

Read My Stories

Too Long; Didn't Read

Make resilience your competitive advantage

5 Graph Patterns To Ace Coding Interviews

About Author

Comments

TOPICS

THIS ARTICLE WAS FEATURED IN

Related Stories

Untitled Story

SOLID Principles In Java: A Beginner's Guide

Top 10 Coding Interview Tips and some Programming Questions to get a Software Developer Job in 2020

13 Ways to Traverse a Tree: Recursion vs Iteration

5 Most Commonly Asked Data Structure Questions in Coding Interviews

5 to 23 Patterns to Ace Any Coding Interview

SOLID Principles In Java: A Beginner's Guide

Top 10 Coding Interview Tips and some Programming Questions to get a Software Developer Job in 2020

13 Ways to Traverse a Tree: Recursion vs Iteration

5 Most Commonly Asked Data Structure Questions in Coding Interviews

5 to 23 Patterns to Ace Any Coding Interview

Light-Mode

Classic

Newspaper

Dark-Mode

Neon Noir

Minty

HN StartUps