All about the graphs [Math Monday]
This is one of the most misunderstood Data Structures
What’s going on my fantastic readers,
We are about to start this week of amazing by starting with one of the highest ROI data structures you will have to learn. When learning about the graph, people often misunderstand why it exists/how to use it effectively. Fear not, we will make sure you understand the philosophy behind the graph. I’ll keep this relatively light on the theory because the internet has plenty of great resources on that (especially FreeCodeCamp). We will also make sure to learn about how to pick the best graph traversal algorithms tomorrow, so make sure you tune in for that. Here, we will focus on the principle behind Graphs, and how you can recognize them. Let’s get shakinn’
Graphs: A dualistic perspective
When I say the word graph, one of three images will pop into your head.
If you’re a stats bro, you’ll think of the charts and plots. Most coding-focused resources ignore this completely. This is a huge mistake
If you’re a graph theory nerd, you will think of the maps with the traveling salesman problem. This helps you visualize the utility of the various (often complex) graph algorithms.
If you are that rare Computer Science person with limited exposure to the other 2, you will think of something defined by an adjacency list. This helps with the coding.
Naturally, what you thought of first will depend on your primary exposure to graphs and what they are. And here is the first reason that people truly struggle with Graphs: All of these definitions are true and useful. Unfortunately, most courses/online resources usually stick to 2 and 3 when talking about Graphs. They completely overlook 1. Why is 1 important for coding purposes?
1 is the true utility of graphs as a data structure. Charts and Plots do a simple task, they communicate some relation between various aspects to us in a direct manner. Think of a simple correlation graph. It’s something I use very regularly for my AI/Statistical Analysis/Machine Learning work. They allow me to check the relationships between multiple features without having to do a lot of math and go through a lot of numbers.
This expression of the relationship between variables goes beyond just numbers. Think of the graphs that represent maps (type 2). Here all we are really representing is the distance between various locations (it’s subtle, but the relationship becomes the distance in this case).
If the map is more nuanced with various kinds of landscapes, then the relationship becomes the effort it takes to go between places (instead of just distance). Do you see how we are tying up all the 3 interpretations of a graph in a single explanation? This is precisely what is important for your coding/coding interviews. You need to be able to switch b/w these 3 perspectives (in reality, all other types are a subset of type 1, but that can be very abstract for non-math people like me). Make sure you reread the section till you get the core point: Graphs can be seen from various perspectives. And each perspective has something unique to the implementation of graphs.
Why you’ve struggled with Graphs
So now to go over the big reason you’re struggling with Graphs. It’s not your fault. Graphs are genuinely hard data structures. Their implementation is not trivial and making the right decisions can be a challenge. No wonder, you (and) many others struggle. Check out this message a reader sent to me.
Add to all this the fact that people haven’t been teaching graphs the correct way. Instead of focusing on why Graphs are important people have spent their hours on the many hows of the graphs. This is why one of the most common feedback I get from my students as we work through problems is not that they found the coding or algorithms challenging, but simply there’s no way they could have figured out they had to use the graph in the question. Think back to this statement. They don’t struggle with the algorithms (case 2) or the coding (case 3). Instead, what trips them up is the usage of the graph (case 1). See the trend? So how can we do better?
How to actually get better at spotting the graph
As mentioned earlier, there are plenty of fantastic resources that will teach you how to actually implement the details and teach you the theory. FCC’s Graphs for Technical Interviews is a lovely video. They also have a 9-hour Graph Theory one, but I doubt most of you care about Graphs beyond the interview/coding context. In terms of ROI, the video covered will give you the details needed.
What nobody teaches you is how to spot whether a problem could be a graph problem. That is what I will cover here. Once I give you a the framework, we will test in some of the trickiest problems in your interviews. Once you see how well this framework handles them all, you can start practicing using it on your own. Since I am an overachiever, I will give you the practice plan that I recommend as well.
Your Graph Spotting Framework
Believe it or not, this is going to be simpler than you are expecting. For this, think back to our earlier statement: Graphs are a very efficient way of encoding and representing relationships between entities.
I want you to change your perspective about a Graph. Nodes, edges, and weights are all correct concepts, but they aren’t useful. What we care about is what they represent. Graphs represent a system. The nodes are the Entities/Citizens in that system. The edges represent a relationship between the citizens. And the weights of these edges just tell us how strong a relationship is. What about unweighted graphs? Just treat them as weighted graphs, where all the edge weights are the same. This helps when it comes to evaluating the correct traversal algorithm.
So how does this framework look? Simply put, we will try to see if the question can be seen as containing all these components. If it doesn't, there’s a good chance that the problem involves Graphs. Even more so if we need to take into account multiple entities simultaneously. Sound too simple? Let’s see this in action against some of the hardest graph problems.
Stress Testing Our Framework
To verify the validity of this approach, we will only take hard questions from Leetcode, which don’t make it obvious that we have to use a graph.
The Alien Dictionary Problem
There is a new alien language which uses the latin alphabet. However, the order among letters are unknown to you. You receive a list of non-empty words from the dictionary, where words are sorted lexicographically by the rules of this new language. Derive the order of letters in this language.
Entities: We know that we want alphabetical ordering of the letters. Thus it is natural to imagine that any system that we come up with will have the letters as the citizens.
Relationships: We want the ordering of letters. Given a letter, it will be important to know what comes after it (which works out well since we have a sorted list given to us).
Weights: There is no difference between two pairs of letters the same difference away. If the ordering for s,v,g in our letter, then the distance s&v== distance b/w v&g.
Here we get a clear indication that a Graph is viable. And the solution actually involves graphs. To stay updated on the solution for this problem, make sure you get a premium subscription. You can get 20% for a whole year using this link
2 SAT Problem
Given a 2-CNF formula, find a way to assign truth values to satisfy it or return False if this is impossible.
My solution to this problem can be found here. Check out to get the details of the solution (it is a very complex problem).We did some math prior to jumping into the graph aspect. Make sure you look at that for the details. But looking at the Graph aspect:
Entities: Different Literals.
Relationships: Implications between literals.
Weights: Once again, there is no degree of implication. All implications are equally “heavy”. Thus the graph has equal weightage in all edges (unweighted)
Word Ladder Problem
A transformation sequence from word beginWord to word endWord using a dictionary wordList is a sequence of words beginWord -> s1 -> s2 -> ... -> sk such that:
Every adjacent pair of words differs by a single letter.
Every
sifor1 <= i <= kis inwordList. Note thatbeginWorddoes not need to be inwordList.sk == endWord
Given two words, beginWord and endWord, and a dictionary wordList, return the number of words in the shortest transformation sequence from beginWord to endWord, or 0 if no such sequence exists.
For eg. given begin=cat and end=bag we can go [cat→bat→bag]. We want to return this.
Entities: Here the entities will be words in the given word list. We are constraining to the words in the list because we know that all the words in the path have to be in the list.
Relationships: We are given that we can only change one letter at a time. Therefore it makes sense to connect words one letter apart.
Weights: Like earlier, there is no difference in 2 distinct pairs one letter apart. Thus unweighted graphs would work here.
If you want me to cover this problem, let me know in the comments below. I’m always happy to cover the problems that trouble my readers.
Practicing Graph Spotting
This is a skill. And skills need to be developed. Here is how I recommend doing it. Start with Easy problems. Start to identify the components of the graph problems, along with how you would set the solution up (don’t focus on coding for this one). Once you can get through 1 in 2-3 minutes, you can move on to the next level. For the hard problems, you can take up to 5 minutes.
The important thing to remember when doing this is to not overdo it. The point is to build your familiarity with graphs and recognizing them.That’s all the goal is. Don’t try to code up solutions because that will take to long (as I’ve covered here, that is actually a mistake). The goal is to get through a lot of examples quickly. Once you can reliably spot an easy/medium level graph hidden in a problem, you have achieved what you needed. Then proceed onwards with the rest of the newsletter and the advice I give you.
That’s it for this week’s Math Monday. This is a simple idea but will be extremely beneficial to your performance.
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