Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
What is graph theory?
3.
Advanced Problems on graph theory
4.
Key Takeaways
Last Updated: Mar 27, 2024
Easy

Important graph problems for Interviews (Advanced Problems)

Author SHIKHAR SONI
0 upvote
Master Power BI using Netflix Data
Speaker
Ashwin Goyal
Product @
18 Jun, 2024 @ 01:30 PM

Introduction

The article discusses and explores important graph problems commonly asked in interviews. In this article, we'll emphasize the more advanced problems (refer to the article on basic problems before this one) and ensure that we cover the more advanced topics required to solve harder problems in contests or interviews.

The article should help you start 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.

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

Advanced Problems on graph theory

1. Implement Dijkstra’s Algorithm.

Refer to the problem Dijkstra's shortest path to practice the problem and understand the approach behind it. It's common to be asked about the time/space complexity of the algorithm and why it doesn't work for negative edge weights. Refer to the article on Dijkstra's algorithm to learn more about the algorithm.

2. Find the minimum cost from source to destination (but you can reduce the cost of one edge)

This problem utilises Dijkstra's algorithm with some modifications. Refer to the article on the problem to get a detailed explanation of its implementation.

3. Find the minimum spanning tree.

Refer to the problem on the minimum spanning tree, try the problem and refer to the approach for help. You can also do the problem using prim's algorithm learn more about Prim's algorithm and Kruskal's algorithm through the related articles.

4. Strongly Connected components using Kosaraju's algorithm and Tarjan's Algorithm.

Refer to the problem on Kosaraju's Algorithm and Tarjan's Algorithm. Try the problem using both methods and observe the differences. 

5. Find the Bridge edge in a graph.

Refer to the problem bridges in a graph to practice the problem and understand its approach.

6. Implement Flood Fill Algorithm.

Refer to the problem flood fill algorithm to practice the problem and understand the approaches behind it.

7. Replace 'O' with 'X'. All the 'O' surrounded by 'X' from all 4 sides will be replaced.

Refer to the problem replace o's with x's to practice the problem and understand its approach.

8. Find the presence of a word in a grid of letters.

Refer to the problem Word Search to practice the problem and understand the approach behind it. As a bonus, try to count the occurrence of the word in the grid. Try the bonus problem word search 2.

9. Write and explain DSU (DIsjoint Set Union).

Refer to Learning DSU learn about DSU so that you can understand them enough to explain how they work. Try to implement Kruskal's algorithm using DSU you learned just now.

10. Smallest Vertex in the Connected Components of all the Vertices in the Given Undirected Graph.

Refer to the article here. It covers the entire approach in detail. This will help you practice a question with a direct application of DSU.

11. Part 3 of word searching in a matrix.

Refer to the problem Word Search 3 to practice the problem and understand its approach. Previously discussed, word search 1 and word search 2 were good starting points before this problem.

12. Critical Connections in a graph

Refer to the critical connection problem to practice the problem and understand its approach.

13. Articulation point, what is it and how to find it.

Refer to the article on articulation points for reference and try to write the code for the following problem by yourself.

14. You are given an alien language (code language) in a sorted dictionary, and you must find the order of alphabets in the language.

Refer to the problem alien dictionary to practice the problem and understand its approach.

15. Solve the problem word ladder.

Refer to the problem word ladder to practice the problem and understand its approach. As a bonus, you can also try word break and try to understand its approach.

16. Number of islands in a grid.

Refer to the problem number of islands 2 to practice the problem and understand the approach behind it. Also, refer to the problem number of islands before attempting this question.

17. What are tries?

Refer to the problem trie implementation to practice the problem and understand its approach. If this is a new topic, refer to the trie related articles here.

18. Find the count of palindromic pairs in an array of strings?

Refer to the problem count palindromic pairs to practice the problem and understand its approach. This question is an application of tries, covered previously.

Key Takeaways

This article extensively discussed the advanced problems that you may encounter in your future interviews and online investments. Refer to learn graphs-1 to learn about graphs as a beginner, Important graph problems for Interviews (Basic Problems) and learn more about graph theory algorithms and terminology used in competitive programming and interviews.

Recommended Problems:

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

Enroll 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!

Previous article
Important graph problems for Interviews (Basic Problems)
Next article
Check whether given degrees of vertices represent a Graph or Tree
Live masterclass