Angol
Graph Algorithms are fundamentally important and different than other Algorithmic domains as it gives an inherent structure to the data and we operate on it. This is one of the most important domains for Coding Interviews focused on problem solving.
Following are some of the problems we have explored which involve ideas to solve a wider range of problems:
• All paths between two vertices
This is a fundamental problem as modifications to it results in solving a wide range of problems.
In the process of formulating a solution, we have explored core ideas like graph traversal techniques like Depth First Search and Graph representation like Adjacency List.
• Mother Vertex
This is an important problem as it highlights two key ideas of Graph problems that is connectivity and importance of specific vertices.
We have solved this problem using two approaches where the efficient approach is a modification of Depth First Search and takes O(V^2) time complexity.
• Paths with K edges
This is an important problem as it demonstrates how we can utilize ideas from Dynamic Programming and Divide and Conquer to solve Graph Problems.
We have demonstrated four approaches where the brute force approach takes O(2^V x V) time, improving it with a structure we get to O(V^K) time, further applying Dynamic Programming to it, we get to O(V^3 * K) time and finally, using Divide and Conquer to optimize calculation, we arrive at O(V^3 * logK) time.
This is a perfect Graph Algorithm problem.
We have covered more variants of the problems and ideas in our conclusion to give a bigger picture and better equip you to solve any problem.
With these problems and the thought process to solve them, you will be fully prepared.
This book has been carefully prepared and reviewed by Top programmers and Algorithmic researchers and members of OpenGenus. We would like to thank Aditya Chatterjee and Ue Kiao for their expertise in this domain and reviews from professors at The University of Tokyo and Tokyo Institute of Technology.
Read this book now and ace your upcoming coding interview. This is a must read for everyone preparing for Coding Interviews at top companies.
Books in this series ("Day before coding Interview"):
• Problems for the day before your coding interview
• Greedy Algorithms for the day before your Coding Interview
• Dynamic Programming for the day before your coding interview
• String Algorithms for the day before your Coding Interview
• Mathematical Algorithms for the day before your Coding Interview
• Graph Algorithms for the day before your Coding Interview
