Coding Interview Prep | 3 MUST KNOW Graph Problem Tips

how's it going everyone hope y'all are doing well so today I have a different type of video for you graph problems are a huge part of the technical interview process so I thought it would be a good idea to give three tips for solving graph problems and I'll be going through full examples for each tip to make sure that it's easily understood so don't forget to Like and subscribe if you want more content like this and without further ado let's get into it all right on to tip number one so this tip is related to the breadth-first search algorithm this search algorithm is very popular across many different interview problems and it's very important to know what data type to use when you're writing your BFS solution so what do I mean by that let's jump into an example so let's say we were to start off with a matrix with the numbers 0 through 8 in many typical graph problems the graphs are represented as matrices where the numbers inside of the matrix are actually the vertices and the index neighbors are the edges so if we were to look at node 2 for example that would be node 2 vertex and the edges of node 2 would be the connection from 2 to 1 and 2 to 5 and also if we wanted to include diagonals we could also include node 4 but for this example let's only include edges as nodes that are horizontal or vertical so that would just be vertice 1 and vertice 5 so if we wanted to perform a breadth-first search on this matrix starting at node 2 we would obviously need to utilize a queue now in order to start this breadth-first search off just like how we discussed we need to add all of the neighbors inside of our queue from our starting node so in this case we're going to add the positions of our neighbors so we'd first add position 0 1 which is corresponding to vertice 1 and then we would add the position 1 2 which corresponds to vertice 5 now in many graph problems you have to decide how you want to represent these coordinates inside of your queue there are many differ ways to represent these coordinates inside of your Q but there is a very easy way to do this and this is universal across any BFS problem so first let's go over all of the different ways that we can represent these coordinates so one of the first ways is to just use a class right we could say class coordinate and then we'd have an X and y coordinate embedded inside of this class now this will obviously work but now you have a lot more boilerplate code to write and in an interview you know you want to try to keep your code as concise as possible so we can exclude this method method number two of representing the coordinates is we could just use a string right we can have the X and y coordinate converted to a string and then we have some sort of delimiter between our X and y coordinate however the problem with this method now is when we want to convert our x and y coordinate back to their integer values we now have to split on this delimiter and perform the conversion from a string to integer once again this involves writing a lot more code which is just unnecessary so we can exclude this method as well so the third way and probably the most common way that I see being used is just to represent the coordinates as an array so this way is completely fine however the one problem I have with it is that once again you're going to be writing a lot of code you have to be initializing new arrays everywhere whenever you are implementing your BFS solution and in an interview you want to try to keep your code as concise as possible you know even saving an extra couple minutes could mean getting the job and not getting the job so although this method is kind of the best of the worst I would still exclude this one and now for my personal favorite method for converting these coordinates it is just to convert these to integer values to a single integer so I'm sure you might be wondering well how do we do that so let's go over an example so what we're going to do is add all of the neighbors from node to inside of our cube the main idea behind this approach we are going to take a 2d mapping to a 1d mapping and in order to do that we need to know how many columns we have in our matrix so in this case we obviously have three columns and our conversion formula from a 2d to 1d would be x times the number of columns plus y so if we were to attempt to add coordinate 0 1 which corresponds to vertice 1 inside of our queue we are going to take that position 0 1 and we're going to apply the formula we're gonna do 0 times 3 plus 1 which equals 1 and that means we can just add 1 inside of our Q now once again we're gonna add the neighbor of node 2 which would be node 5 which corresponds to the position 1 2 if we apply the formula that will be 1 times 3 plus 2 which equals 5 and that means we can add 5 inside of our Q now one of the last things we're going to want to do is when we pull from the Q we need to convert this 1d integer back to our 2d coordinate because obviously this 1d integer means nothing to us in the context of a 2d matrix we need an x and y coordinate in order to continue our BFS so let's say we were to pull the number 1 from our queue our 1 d2 to d4 mule ax would be the following the row would be our index the number that we just pulled from our Q divided by the number of columns we have and then the column number would be the index mod the number of columns that we have so now with both of these formulas were able to do conversions from 1d to 2d and vice versa so if we were to apply this logic to the number 1 we would do 1 divided by 3 which would be equal to 0 that's our row and then we do 1 mod 3 which is 1 so now as you can see this number 1 we've successfully converted back to our original coordinate of 0 1 which corresponds to our number 1 vertice likewise if we were to perform the same logic on the value 5 we're going to do 5 divided by 3 which would be 1 and then 5 mod 3 which would be 2 and now we have the coordinate 1 2 which corresponds to the vertice 5 so although this method does involve the use of formulas they aren't too complicated to understand and they will allow you to write far less code when you're implementing your BFS solution on to tip number 2 so this tip is also relating to the breadth first search algorithm and it's going to allow you to write your BFS solution in a much cleaner and faster way let's look at the same matrix and look at vertice number 4 Mirta seen um burr 4 has connections to 1 3 5 and 7 now just like we discuss a breadth-first search we'll have to check all the neighbors add them inside of the queue and what that means is that we need to look in the upwards position left-right and down and we have to perform that logic for every single vertice that we come across so if we were to look at some pseudocode for a BFS it would look something like this we would first pull from our queue so in this case if we were to look at vertice 4 we would pull the coordinates 1 1 and now that we have those row and column numbers we would then have to calculate what the left right up and down coordinates are and now for every single direction we're going to need to check if that position is even valid if it is we need to add that position to our queue and add the position to our visited set so as you can see from this code where we're checking if the position is valid and adding it into our data structures this code is duplicated across each direction that we're checking and this is a very common way that I see people solve breadth-first search problems however there is a much easier way to write this that will not affect your time or space complexity so we have the old way on the left and for the new way we're also going to be utilizing the queue as normal and we're going to be pulling from our queue just like how we are in the old version but now in the new version the difference is we're going to create a 2d array which will hold all of the directions that we're going to need to check so these directions the inner arrays inside of directions is equivalent to the left/right up/down in the old version that we initialized at the top as you can see they're essentially doing the same thing for example if we look at left on the old it's saying that okay we want the row and column minus one well if we look at the new version if we look at the left array all it's saying is okay the row we're going to keep it at zero but the column we're going to subtract it by one and the same logic applies for all of the other directions and now once we initialize this directions array we can then loop over each array and once we extract each direction we then append it to the row and column that we pulled from our queue so now with this new x and y value that we've just calculated we can then just check if that x and y coordinate is valid if it is then that means we can add it inside of our queue and add it inside of our visited set so as you can see the new way will allow you to reduce the amount of code that you have to write and it's going to simplify the logic for you when you're implementing your breadth-first search solution onto our last tip tip number three this is relating to really any general graph problem and that is to use your input to your function as a way to keep track of previous calculations that you've made so once again let's jump into example so this makes more sense so let's say we have the following matrix and this matrix only contains numbers that are zeros or ones and what this means is that our input to this function is actually restricted in many graph questions you'll find that the problem at hand is to search through this given input and maybe find the maximum of something minimum of something and it's usually on a restricted input as you are traversing through all of these nodes in this graph you will usually have a set to keep track of visited elements that you have come across so let's say we were traversing over this matrix and every time we encounter an element we would add those positions to the visited set so in this case we visit the position zero zero so we add it to our visited set we visit zero one zero two one zero and every single coordinate we add into our visited set to ensure that we don't go back to those positions however since our input is restricted to only zeros and ones there's actually no need to even initialize a visited set at all let's say we were to loop over this input again but instead of adding the coordinates to a visited set we just changed the element to something outside of the bounds of our restricted area so in this case to mark something as visited we just change the current position to something that is not a zero or one so in this case we can just change it to a two likewise when we go to position zero one we just mark it as a two position zero two we mark it as a two and so on and so forth so pretty much this tip entirely boils down to if our input is restricted then there's really no set needed we can just use our input as our set by changing our elements to something that is outside the bounds of our restricted input and this is definitely something that you would want to clarify with your interviewer to make sure that you're even allowed to do this there may be a scenario where you are told that you are not allowed to modify your input and then this would not work but if you can use it this will actually reduce your space complexity because you don't have to initialize an extra structure so that is it for this video guys I hope these tips were helpful for you graph problems can be a real pain to complete but I feel like with these tips it does make them a bit easier to manage also if you want I have a private discord channel that you can sign up for on my patreon where you can ask me questions and ask other people questions in community well that is all I have for you guys and I will see you guys in the next one

Channel: Michael Muinos

Views: 10,427

Keywords: coding, software engineering, graph problems, coding interview prep, coding interview preparation, coding interview tips, software engineering tips, algorithms, breadth first search, depth first search, search algorithms, leetcode

Id: tMSdjPKFRD4

Length: 13min 26sec (806 seconds)

Published: Fri Jun 19 2020