Important graph problems for Interviews (Basic Problems)

SHIKHAR SONI
Last Updated: May 13, 2022
Difficulty Level :
EASY

Introduction

The article discusses and explores important graph problems commonly asked in interviews. In this particular article, we'll emphasise the easier problems and ensure that we cover the basics required to solve a good number of problems on graphs in an interview.

The article should help you get started with problem-solving if you are new to graph problems.

What is graph theory?

Graphs are a tool that can help enable us to model and study various pairwise relationships between objects/entities. If you want to model your family tree, the structure you make is a special case of a graph (a tree), and it enables you to represent the relationship between them easily. Graph Theory is the study of graphs.

Problems to help you get started with graph theory

1. Print the adjacency matrix and the adjacency list of a graph.

Refer to the article on various graph representation methods to learn more about various such methods. Refer to the article implementation of graph representations for the implementation details.

2. Print a DFS traversal of a graph.

This problem utilises the depth-first search algorithm. Try the problem by doing dfs traversal, which also covers the approach to do the problem if you get stuck.

3. Print a BFS traversal of a graph.

This problem utilises the breadth-first search algorithm. Try the problem bfs in a graph that also covers the approach to do the problem if you get stuck.

4. Find Transitive Closure of a graph.

Refer to the problem, transitive closure of a directed graph to practice the problem and understand the approach behind it.

5. Find the number of connected components in a directed graph.

This problem can be solved with 3 different methods. You can try the problem by doing the problem, finding the number of states and learning about all the various methods.

6. Find the number of connected components in an undirected graph.

This problem is commonly asked in various interviews, usually not directly, but it's an important stepping stone. Try to solve the problem using the 3 methods discussed for (5).

7. Find the number of '0' islands in a binary matrix (containing only '1' and '0').

This problem utilises the ideas covered in problem 6, and you can try it by doing the problem count islands.

8. Detect a cycle in an undirected graph.

This problem again directly applies graph traversal algorithms. Refer here to solve the problem detect cycle in an undirected graph. The approach covers the BFS method. Try solving the problem using DFS.

9. Print a topological sort of a directed acyclic graph. (As a bonus, you can try printing the lexicographically minimum topological sort)

This problem can be done using different algorithms (Kahn's Algorithm, modified DFS, etc.). Check out the topo sort problem and try solving it. Here is the article on Kahn's algorithm for reference.

HINT: The bonus problem can be solved using Kahn's Algorithm and a min-heap.

10. You are given N tasks, and certain tasks have prerequisites (these prerequisites must be completed before completing that task). Find if it's possible to complete the set of tasks and if it's possible, print an order in which you can complete all the tasks.

The set of tasks can only be completed if the graph is a DAG (directed acyclic graph), and the next task is to print the topological sort for the graph (if it's a DAG).

11. Print the Hamiltonian Cycle in a graph.

Refer to the problem find hamiltonian cycle and refer to the optimised approach for the implementation and explanation of the approach. Refer to Euler and hamiltonian paths as prerequisites for solving the problem.

12. Find if an array of strings (words) can be arranged into a cycle.

Refer to the problem circle of words to practise the problem and understand the approach behind it.

13. A snake and ladder board is given as input to find the minimum number of dice moves required to reach the bottom-leftmost point to the top-rightmost point.

Refer to the problem snake and ladder to practise the problem and understand the approach behind it.

14. Given a graph, determine if the graph is bipartite.

Refer to the problem check if graph is bipartite to practise the problem and understand the approach behind it. Refer to the article on bipartite graphs as a prerequisite.

15. Find the maximum bipartite matching in a graph.

The problem is a good exercise after the previous problem. This problem can be solved using the Ford Fulkerson algorithm or Kuhn's Algorithm. Refer to the article on Ford Fulkerson and min-cut for reference.

16. Detect the presence of a cycle in a directed graph.

Refer to the problem on detect cycles in a directed graph to practise the problem and understand the approach behind it.

17. Find whether a path exists between two vertices.

Refer to the problem, check if a path exists to solve the problem and understand the approach behind it.

18. Find the node level in a tree rooted at some node.

Refer to the problem on node level to practise the problem and understand the approach behind it.

19. Print all the possible paths between two vertices in a graph.

Refer to the article on printing all paths from a source to a destination vertex to understand the approach in detail with implementation to help you understand it better.

20. Distance of nearest cell in a binary matrix (containing 0 and 1 only) to the cell having 1 in it.

Refer to the problem of finding the distance between nearest 1 to practise the problem and understand the approach behind it.

21. A grid contains fresh and rotten oranges. Every second, all oranges adjacent to the rotten ones also become rotten. Find the minimum time before which all oranges become rotten, or print -1 if it's impossible for all oranges to become rotten.

Refer to the problem rotting oranges to practise the problem and understand the approach behind it. The problem's approach is very similar to the previous question.

22. Find the minimum number swaps required to sort an array (you can swap any two indices).

Refer to the problem on minimum swaps required to practise the problem and understand the approach behind it.

23. Find the minimum number of steps a knight requires to reach a square on a grid.

Refer to the problem on minimum steps to reach the target by a knight to practise the problem and understand its approach. In problems like these, instead of using Dijkstra, bellman ford, etc., we will be using BFS to find the minimum distance in an unweighted graph.

Key Takeaways

In this article, we have extensively discussed the basic problems that you may encounter in your future interviews and online contests. Refer to learn graphs-1 to learn about graphs as a beginner and learn more about graph theory algorithms and terminology used in competitive programming and interviews.

Refer to our guided paths on Codestudio to learn more about DSA, Competitive Programming, JavaScript, System Design, etc. 

Enrol in our courses and refer to the mock test and problems available.

Take a look at the interview experiences and interview bundle for placement preparations.

Do upvote our blog to help other ninjas grow. 

Happy Coding!

Was this article helpful ?
0 upvotes