There’s a type of graph problem that no one talks about, but it makes up more than half of all graph problems. And if you don’t learn how to solve these problems, you’ll fail most graph interviews.
When we talk about graphs, we usually see stuff like this:
- Depth-first search
- Breadth-first search
- Topological sort
- Dijkstra’s algorithm
And while these algorithms are definitely important, they’re also pretty clearly defined. If you have a graph and you understand the algorithm, then you can write the code.
But what if you don’t even know that the problem is a graph problem? How do you look at a problem about counting islands or whether a puzzle is solvable and say “yep, that’s a graph problem?”
The answer is that you have to understand implicit graphs.
Implicit graphs are graph problems where the graph is defined implicitly by the data itself. A graph is just data points that are connected together in some way, and in tons of real world scenarios we can have data that is connected without us being explicitly told.
Here’s a simple example:
Imagine you have a list of people in an apartment building and what floor they live on? You could construct a graph of this data because all these people are “connected” by living on the same floor.
Or let’s say that you’re playing a game of chess. If you consider the current board position to be one data point, every possible move that you makes leads to another board state that is “connected” to the current board. Knowing the rules of chess, we could generate a massive graph that would show every different series of moves the game could take.
Source: https://medium.com/@SereneBiologist/the-anatomy-of-a-chess-ai-2087d0d565
Now these are two simple examples of how graphs come up in the real world, but more importantly we have to ask two question:
- How do we identify when something is a graph problem?
and - Once we identify that, how do we solve it?
These are the sorts of questions that, yeah, once you understand this well enough you can just deduce on your own.
But honestly, in an interview, time is so critical that having some patterns or heuristics is key. And that’s exactly how we get people up to speed in their interviews so fast at Byte by Byte.
In the case of implicit graph problems, there are 3 patterns that you can identify:
- Grouping Problems
- Solvability Problems
- Ordering Problems
In this video, I’m going to take you through the high level of each of these so that you understand the pattern and how to apply it and then in future videos we’ll get into the code and all that good stuff.
Grouping Problems
Grouping problems are any sorts of problems where we’re looking at subgroups of our data.
The classic example of this is the Number of Islands problem.
In this problem, we have a grid that represents a map of land and water and we want to determine the number of disconnected islands. In this example, you can visually see that there are 2.
Now how is this a graph problem?
Even though it isn’t defined as a graph problem, the points of land are connected based on their location, just like our people living on different apartment floors. Therefore we can connect the land to generate a graph like this.
Once we see this is a graph, all we have to do is find all the connected components using some sort of search. You do need to be sure you know how to do this, but this goes back to one of our core graph algorithms that you just need to study.
If you want to try this out for yourself, here are examples of other grouping problems:
Solvability Problems
The second type of implicit graph problem is a solvability or pathing problem. A lot of problems fall into this category.
Most problems that ask you “what is the minimum number of steps to X” or “is there a valid way to Y” can fit into this category.
Let’s look at one of my favorite examples, the sliding puzzle.
In this problem, we’re given a puzzle that looks like this, and we want to determine the minimum number of moves to solve the puzzle. We’re allowed to move tiles horizontally and vertically into the empty space.
We can start by asking “how do we translate this into a graph?”
Well, if you think back to the chess example from earlier, you’ll remember that we have our current board state and we have a defined set of moves that we can take. That means that we can start to build out a graph that looks like this.
We have our starting state, then all the states that we can get to from there, and then we can continue to build out the full set of connected states.
And once we’ve done this, our problem becomes as simple as finding the shortest path between our start state and the “solved” state.
Let’s also look at another toy example so that you can see a totally different way in which to apply this approach.
Say we have a string and we want to find the minimum number of characters to remove so that the string is entirely made up of a single character. So in this case “aabca” would become “aaa”, so our answer would be 2, since we remove the ‘b’ and ‘c’.
Obviously there are non-graph ways to solve this, but let’s consider it from a graph perspective.
In this case, our state is the string itself. And what are the adjacent states?
Well we can just try removing each character from the string.
If we repeat this process, then we end up with a graph that looks something like this, and from here, we just need to find the shortest path from our starting point to any string that matches our condition of being all one character.
Here’s what our path might look like.
Because this solvability pattern comes up so frequently, I want to give you a general framework for it. That way you’ll be prepared whenever you see something like this in your interview:
- Define the states of your data. In the case of our sliding puzzle, this was the board positions. For our string example, it was just the strings. The key is that you need to capture the complete state because you’ll need to look at this state and evaluate whether it is the win-condition or not
- Define the connections between the data. These are the moves that you can make to get from one state to the next.
- And finally, perform a graph search to find the path between the starting state and the win-condition. If you want to find the shortest path, this should be BFS. If you want to find all paths, DFS is usually easier.
If you know how to use this framework, it will open up a ton of possibilities in your interviews.
Here are some additional practice problems:
Ordering Problems
The final pattern for implicit graph problems that comes up often is ordering problems. If you ever see a question that asks “given some set of dependencies, what is a valid ordering of data points?”, then that’s an ordering problem.
The classic example of this is scheduling. For example, let’s take a look at this Course Scheduling problem. In this problem, we’re given a list of courses and their prerequisites and we need to determine whether there is a valid order in which we can take these courses so that all the prereqs are properly met.
Let’s start by translating this into a graph. We have our courses. Those are the data points. And then we have our prerequisites. We can draw these in as directional edges where the course points to its prerequisite.
Now that we have this graph, the question just becomes “how do we find the ordering that puts all the prerequisites first?” and the answer is that we actually have a tool for that, which is topological sort.
Like with the other examples here, I don’t want to get super into the weeds, but let’s quickly go through how this works. To do our topological sort, we’re just going to repeatedly find any nodes that don’t have any dependencies and remove them as well as any edges to them.
Effectively what we’re doing is saying “find a course I’m allowed to take and take it. Then see what other courses I’m allowed to take and repeat.”
When we do this, in this example we can see that we get a valid ordering.
Now implementing topological sort isn’t trivial to do, so I definitely recommend taking the time to review and we’ll cover that in an upcoming video, but once you have that down, solving these problems becomes relatively simple.
As with the others, here are some additional problems you can try:
If you understand the three patterns that we covered, you’ll be in great shape to solve implicit graph problems in your interviews. These patterns will allow you to easily identify the problems and give you a clear path forward to solve them.
