In our exclusive tech-focused MicroClass, Omkar Deshpande, Head of Curriculum at Interview Kickstart, navigated students through the fundamentals of Graph Theory and Graph Traversal Algorithms.
Graphs is a complex and large technical topic that requires you to devote a fair amount of time in preparation to comfortably solve probelms. Using a structured approach to your interview prep will help you tackle tough problems that you might not have encountered before, plainly by applying sound fundamentals and recognizing patterns in them. As for Graphs, the code for more complex problems should be built from code for fundamental problems.
Let’s dive right into it and look at what was covered during the session.
Top Take-aways from the MicroClass
The Origin of Graph Theory
Omkar kickstarted his session by introducing the origin of Graph Theory. He spoke about how the eminent Swiss Mathematician Leonhard Euler solved the famous Konigsberg Bridge Problem using “Graph Theory”. Konigsberg, a Russian city seated on the Pregel River, had 7 bridges connecting four different regions of the city. People wondered if it was possible to begin at one point and traverse the whole city through the 7 bridges, without crossing any bridge twice, and return to the starting point. Euler solved this problem using “Graph Theory”, and the concept evolved to be applied in present-day mathematics and computer algorithms.
Questions on Graphs are common at FAANG interviews
The importance of Graphs in technical interviews was emphasized, especially for FAANG companies. Omkar introduced the fundamentals of “Basic Graph Theory” and how Graph representations can be carried out.
General Graph Traversal Algorithms
BFS and DFS, the most common algorithms used to traverse a graph and search for nodes in trees and graphs, was introduced. The speaker explained how to navigate the shortest path through Breadth First Search, and how to perform sorting through Depth First Search.
Directed and Undirected Graphs
The fundamental approach to how BFS and DFS can be carried out differently for both Directed as well as Undirected Graphs was elucidated. Connected Components and Detecting Cycles were also made clear.
Advanced Graph Algorithms
Some advanced Graph algorithms, including Kahn’s Topological Sort Algorithm, Tarjan Kosaraju algorithm and Greedy algorithms were explained. Some basic problems pertaining to the application of these algorithms were also elucidated.
Approach to Interview Prep
The speaker specifically asserted the importance of a structured and organized approach that involves dedicated problem-solving in various subtopics. As Graphs is quite an extensive topic that contains several sub-topics hopping into it haphazardly in a random fashion and switching between subtopics can hamper progress efforts. The code for later and more complex problems should be built on code for easier problems.
Also, advanced and more complex coding problems on Graphs should be solved after studying Dynamic Programming and Greedy Algorithms with simpler inputs. Doing otherwise will end in failing to recognize inherent patterns in Graph problems, making it significantly difficult to solve tough questions.
Types of Problems to Expect
A few types of Graph problems that commonly appear at these interviews were explained. These included:
- Performing DFS on Directed Graphs where Trees are more complex
- Problems on Bridges, Articulation Points, and Detecting Back Edges
- Performing Topological Sort using different Graph Algorithms.
- The Flood-fill and Grid Problems
- Problems pertaining to the Get Neighbors Function
- Questions on the Tarjan Kosaraju Algorithm
- Questions on Union Weighted Graphs
- Questions pertaining to Kahn’s Topological Sort Algorithm
Top Question Asked at the MicroClass
- I’ve been practicing Graph questions on IK and Leetcode. I’m unable to decide whether to use DFS or BFS, and I get stuck because of that. For example, there was a question that required using Tarjan’s Algorithm. How do I go about it?
A. Most Graph questions require the use of standard Graph algorithms, since it is very hard to design a new Graph algorithm from scratch. Tarjan's algorithm is an
advanced application of DFS. By getting exposure to all standard Graph algorithms that a typical undergraduate course covers, and learning to code them up, you can be assured that the algorithm itself won't be a mysterious secret. It is however important to understand how to design Tarjan's algorithm or Dijkstra's algorithm or any other advanced algorithm, rather than memorize them by name. The names are secondary, it's the design of the algorithm that is important. Greedy and Dynamic programming algorithms on graphs should be learnt after using those techniques on simpler (non-graph) inputs.
Tarjan's algorithm uses arrival and departure times with DFS and so you need to understand the simpler properties of the DFS tree that arrival and departure times reveal. Then you use them to infer more complex properties.
Finding bridges, articulation points and strongly connected components are standard textbook problems. If you read any good algorithms textbook, you would be exposed to those problems.