How to Figure out the correct distance finding algorithm [Technique Tuesday]
There are so many. How do we know the correct one?
Hello my Graph lovers,
As promised in yesterday’s Math Monday about Graphs and earlier posts, I will now be covering a topic that a lot of people struggle with. How do we even out the correct graph traversal algorithm? Fear not, by the end of this email/post you will be able to look at a graph and tell immediately what kind of a traversal algorithm you will need.
The important algorithms
I am a huge believer in the 80-20 principle. The principle states that 80% of your results come from 20% of the work. This principle is even more extreme for Graph Traversal Algorithms. Believe it or not, you can almost guarantee success by just learning 5 algorithms. That’s it. Here they are in the order of importance.
BFS/DFS- These are the two you have to know. These are the most foundational algorithms in Graph Traversal. Many problems also can be reduced to BFS/DFS algorithms. These two also form the basis for other more complicated graph algorithms, so you have to be very comfortable with them
Topological Sort- This is prone to show up from time to time. You can actually derive this from DFS, but it’s better if you know it beforehand. That way you can make the connection much quicker.
Djikstra’s Algorithm and A*- These are variants of BFS, developed to find the shortest paths in questions that involve weighted graphs. Even though they look intimidating at first, once you master BFS, these become relatively straightforward. If you are somebody interested in AI (especially self-driving cars), then these algorithms become crucial.
These are the concepts that you will need for your interviews. As you can see BFS/DFS are clearly the most important of the bunch. Therefore, focus on mastering them first, before moving on to the others.
The Framework
Time to get into what you’ve all been looking forward to. If you look online, you will be met with intimidating discussions throwing around terms like “branching factor”. This is where coding interviews become simpler than the many nuances of real-life implementations. Here are some quick pointers:
Finding the shortest path: For shortest path problems, BFS (for unweighted graphs) or A* (for weighted graphs) will be your best bet. DFS does not guarantee the shortest path, and Djikstra’s is generally worse than A* (learning it is helpful to understanding A*, which is why it’s in the list).
Visiting the complete graph: For problems where we have to take into account the entire graph (alien dictionary, detecting a cycle etc.), then DFS becomes your best friend. It takes lesser memory.
Following is a very big discussion of the same. If you’re someone looking to go deeper (see what I did there?) into graphs, check it out. The above checklist is going to be enough for the rest of us though. Go through and take a look at the questions on Leetcode. Once you know this pattern, you’ll be shocked how many fall easily into this pattern. For any you don’t see, just drop them in the comments/message me and I can explain them. But you will find this framework will help you easily identify the correct algorithm in practically every case.
Obviously, to get to this stage, you need to learn to identify a question as a graph problem and represent it as such. This is something that requires practice. You will need theoretical knowledge, as well as knowledge of how to build up to these situations. For the former, make sure you check in with Math Mondays. The solutions we cover in this newsletter will help you convert that knowledge into results. Get access to solutions and other premium content, by subscribing here and getting 20% off for a whole year.
Now that you have know this system, use the plan mentioned above to put it into practice and get good with it. Remember to work in other Data Structures and Questions as well (about 30% of your questions at most should be from one topic). Only focusing on one topic is a mistake, unless you’re told to do so. And make sure to regularly check in with this newsletter on Thursdays as I cover detailed solutions to questions asked by top-tech companies.
That’s it for this week’s Technique Tuesday. Use this framework to be able to identify the correct approach at a glance.
If you liked this post, make sure you fill out this survey. It’s anonymous and will take 2 minutes of your time. It will help me understand you better, allowing for better content.
https://forms.gle/XfTXSjnC8W2wR9qT9
Happy Prep. I’ll see you at your dream job.
The One who sees Graphs everywhere,
Devansh <3
To make sure you get the most out of Math Mondays, make sure you’re checking in the rest of the days as well. Leverage all the techniques I have discovered through my successful tutoring to easily succeed in your interviews and save your time and energy by joining the premium subscribers down below. Get a discount (for a whole year) using the button below
Reach out to me on:
Instagram: https://www.instagram.com/iseethings404/
Message me on Twitter: https://twitter.com/Machine01776819
My LinkedIn: https://www.linkedin.com/in/devansh-devansh-516004168/
My content:
Read my articles: https://rb.gy/zn1aiu
My YouTube: https://rb.gy/88iwdd
Get a free stock on Robinhood. No risk to you, so not using the link is losing free money: https://join.robinhood.com/fnud75