Register for our webinar

How to Nail your next Technical Interview

1 hour
Loading...
1
Enter details
2
Select webinar slot
*Invalid Name
*Invalid Name
By sharing your contact details, you agree to our privacy policy.
Step 1
Step 2
Congratulations!
You have registered for our webinar
check-mark
Oops! Something went wrong while submitting the form.
1
Enter details
2
Select webinar slot
*All webinar slots are in the Asia/Kolkata timezone
Step 1
Step 2
check-mark
Confirmed
You are scheduled with Interview Kickstart.
Redirecting...
Oops! Something went wrong while submitting the form.
close-icon
Iks white logo

You may be missing out on a 66.5% salary hike*

Nick Camilleri

Head of Career Skills Development & Coaching
*Based on past data of successful IK students
Iks white logo
Help us know you better!

How many years of coding experience do you have?

Thank you! Your submission has been received!
Oops! Something went wrong while submitting the form.
Iks white logo

FREE course on 'Sorting Algorithms' by Omkar Deshpande (Stanford PhD, Head of Curriculum, IK)

Thank you! Please check your inbox for the course details.
Oops! Something went wrong while submitting the form.
Our June 2021 cohorts are filling up quickly. Join our free webinar to Uplevel your career
close

UpLevel MicroClass Highlights: Graphs for Technical Interviews

Last updated on: 
September 6, 2023
|
by 
Dipen Dadhaniya
The fast well prepared banner
About The Author!
Dipen Dadhaniya
Dipen Dadhaniya
Engineering Manager at Interview Kickstart. A passionate and versatile web developer packed with full-stack development skills and a curiosity to explore computer languages.

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.

Here's what we’ll take you through:

  1. Top Take-aways from the MicroClass
  2. Questions on Graphs are common at FAANG interviews
  3. Approach to Interview Prep
  4. Types of Problems to Expect
  5. Top Question Asked at the MicroClass

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

  1. 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.

 


Posted on 
July 10, 2020
AUTHOR

Dipen Dadhaniya

Engineering Manager at Interview Kickstart

Attend our Free Webinar on How to Nail Your Next Technical Interview

Square

Worried About Failing Tech Interviews?

Attend our webinar on
"How to nail your next tech interview" and learn

Ryan-image
Hosted By
Ryan Valles
Founder, Interview Kickstart
blue tick
Our tried & tested strategy for cracking interviews
blue tick
How FAANG hiring process works
blue tick
The 4 areas you must prepare for
blue tick
How you can accelerate your learnings
Register for Webinar

Recent Articles

entroll-image