What do you think?
Rate this book
Graph Algorithms for the day before your coding interview
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
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
45 pages, Paperback
First published June 7, 2020
23 people are currently reading
9 people want to read
About the author
Aditya Chatterjee
94 books8 followersAditya Chatterjee is an Independent Algorithmic Researcher, Software Developer and Technical Author. He is the founding member of OPENGENUS, an organization focused on changing Internet consumption.
Since 1990s, he has been involved, actively, in the growth of Computing in Japan. Major computational advances have been made in the last 3 decades which reformed not only education infrastructure but also the competitive programming community.
He has collaborated with over 500 researchers and has mentored over 3000 learners personally across the Globe through the Internship program at OPENGENUS.
Since 1990s, he has been involved, actively, in the growth of Computing in Japan. Major computational advances have been made in the last 3 decades which reformed not only education infrastructure but also the competitive programming community.
He has collaborated with over 500 researchers and has mentored over 3000 learners personally across the Globe through the Internship program at OPENGENUS.
Ratings & Reviews
Friends & Following
Create a free account to discover what your friends think of this book!
Community Reviews
Displaying 1 of 1 review
July 12, 2023
Sí es literalmente un conjunto de algoritmos sobre grafos que te puedes estudiar el día anterior a una entrevista para entrar a trabajar.
Te da las bases suficientes para defenderte en una entrevista si alguien te pregunta, pero también te hace entender los conceptos fundamentales para poder construir conocimiento sobre esto y resolver problemas más complejos.
Además se toman el tiempo de explicarte lo suficiente para que no te quedes en el aire. Los algoritmos que ve son:
- Encontrar un camino del nodo A al B
- Encontrar todos los caminos del nodo A al B
- Encontrar todos los caminos de tamaño K del nodo A al B
- Encontrar un nodo madre (un nodo desde el que puede llegar a todos los otros nodos)
Creo que leído con detenimiento, dedicándole un día entero te puede ayudar a sí pasar una entrevista sobre este tipo de algoritmos.
Te da las bases suficientes para defenderte en una entrevista si alguien te pregunta, pero también te hace entender los conceptos fundamentales para poder construir conocimiento sobre esto y resolver problemas más complejos.
Además se toman el tiempo de explicarte lo suficiente para que no te quedes en el aire. Los algoritmos que ve son:
- Encontrar un camino del nodo A al B
- Encontrar todos los caminos del nodo A al B
- Encontrar todos los caminos de tamaño K del nodo A al B
- Encontrar un nodo madre (un nodo desde el que puede llegar a todos los otros nodos)
Creo que leído con detenimiento, dedicándole un día entero te puede ayudar a sí pasar una entrevista sobre este tipo de algoritmos.
Displaying 1 of 1 review