Problem Solving Techniques For Programming - How To Actually Get Good
today I'll be sharing with you my tips tricks and advice for getting better at solving problems now in my opinion problem solving is one of the most important skills that you can have especially as a programmer and actually I'm not the only one that agrees with this the largest tech companies in the world evaluate you almost entirely based on your problem solving ability and that's why we have the famous coding interviews so in this video I'm going to walk you through the entire process of breaking down a problem solving it right from the beginning until the very end we're going to start by understanding the problem we're then going to develop an algorithm to solve it and then I'm going to code this out live in front of you so you can see exactly how an experienced programmer goes about solving these types of problems the specific problem we'll look at will be a medium level question from leak code these are the type of problems you'll probably get during a coding interview it will make a good example so you can understand how to solve something that's not super easy yet not extremely complicated however before we get into that I know that the reason a lot of you are watching this video is because you want to land a software development position now I won't lie to you in 2024 it's a lot different to land a role than it was even just a few years ago and it can be really really competitive now that's actually why I teamed up with HubSpot and wrote an entirely free guide called how to land a developer role in the world of AI drawing on my over a decade of experience this summary covers the best programming languages to master and the most effective ways to learn them it also goes over best practi practices for your resume how to create your portfolio and recommendations for YouTube channels and other resources to enhance your development skills you can check it out for free from the link in the description personally my favorite part is the long list of resources including YouTube channels and websites that showcase fantastic free ways to improve your skills this content is focused on helping you distinguish yourself as a programmer in this AI era offering essential insights and strategies to help you remain competitive in the developer industry I'm thrilled to collaborate with HubSpot on this resource and to have them sponsor this video enabling me to provide all kinds of free content like this video to you so let's begin here by going to the computer and having a look at a problem that I've selected now this problem is called rotate list it's a medium problem on Le code and again most of the time you'll be given medium type problems this one is not extremely difficult but it's actually a really good fit for this video because it won't take us super long to solve but you'll get an idea of how we go through the process so the first thing we want to do if we're in a coding interview situation or really just trying to break down any problem is we want to make sure we have a thorough understanding of what the problem is in a lot of situations the problem will be read to you in that case feel free to ask for clarification sorry ask them to repeat themselves and just make sure you really understand it before we start solving in this case I'll kind of read it to you as we go from the prompt on the Le hand side of the screen so it says given the head of a linked list rotate the list to the right by K places and it shows us a visual example which is quite helpful you can see the original list 1 2 3 4 5 and if we're rotating by two which is the example right here then you'll see that the rotation ends up with 4 5 1 2 3 so this is pretty straightforward we're taking the K elements from the end of the list and then rotating them to the front of the list or whatever way you want to look at it as but that's kind of the way that I see it I see 1 2 3 4 5 I see the first rotation five goes to the front and I see in the second rotation four goes before five k equals 2 so we've taken those two back elements and kind of just placed them at the front going down we can see we have example number two now this one's a bit more complicated where we have k equal 4 that's the amount of rotations in this case I notice immediately that four rotations is more than the length of the list which is three and you can see that when we end up rotating this we get kind of a different result where we need to rotate multiple times and we end up eventually hitting the original list you can see we have 0 one2 we do one rotation two rotation three rotations which brings us back to the original list and then we have two 01 so we also see that we have some constraints here we can read through those if we want but overall a pretty easy problem to understand but I would want to make sure again that I'm clarifying this with my interviewer so if I was in the interview situation I would be asking them okay is there a maximum length for the linked list could you be sending me a linked list that maybe has no elements inside of it or just has one element can K be a negative value or does it have to be a positive value I know these might seem like silly questions but a lot of times interviewers really want to see that you're trying to narrow the problem down as much as possible and really make sure you account for all of the possible edge cases or different considerations you might assume something I'd say never assume instead just ask the interviewer no question is really a bad question and usually you spend the first few minutes kind of talking back and forth about the problem and just showing them that you do really want to make sure you understand it before you start solving it so now that we have kind of a somewhat decent understanding of the problem what I'm going to do is actually go over to the Whiteboard this is what I would always do when I'm solving a problem and I'm going to start drawing a few things out and kind of visualizing my thought process one because it's helpful for me but two because it's helpful for anyone else that's watching this like an interviewer to understand how I'm actually about to solve the problem I always find it a lot easier to kind of draw things out diagram it even if it's a bit messy so let's go ahead and do that so I'm on my iPad now and I'm going to start walking you through exactly what I would do to solve this problem now I would always start by just writing out some kind of case or example on my whiteboard or on my drawing tablet just so that I can walk through it slowly and really make sure I understand this and also just do a few different cases that maybe haven't been given to me it's always a good idea to take some inputs and just figure out what the output should be and if you can do this kind of visually by writing it out then it's going to help you actually devise an algorithm to solve this so when I look at this I see that I have 1 2 3 4 5 I have K = 3 we know this is very similar to the other input that we were given and we know this is going to be 3 4 5 1 and two now when I look at this a few things come to my head the first thing that I realize is that I kind of have the beginning first two elements here and I have the ending three elements here now what this tells me is that actually there's kind of two ways I can approach this problem I can take the first two elements and I can move them to the back or I can take the back three elements and I can move them to the front just because it says rotate right doesn't mean that I actually can't rotate to the left and just do kind of a different approach or not really rotate to the left but I doesn't really dictate the order in which I need to rotate the elements and it's perfectly valid if I were to take these to and put them at the end because that's going to give me the same result so just something that's coming into my head this is what I would be kind of talking about with the interviewer even if it doesn't really make sense yet I'm kind of walking through how I'm going to reach the solution and this thought process this is what people want to see they want to understand how you're actually solving the problem okay so that's kind of an interesting note that we had and now that I've done that and this is pretty easy I'm going to start looking for a few different edge cases or things that might mess up potential Solutions so for example I'm going to go with something like k equals 7 now the first thing I notice when I see k equals 7 is that 7 is greater than the length of my link list in this case I just have five elements now that kind of intuitively tells me that if I do this many rotations a eventually I'm going to reach a linked list that's the exact same as the starting linked list so it really doesn't make sense for me to do any rotations that are greater than the length of my link list which means I can probably simplify this K value and get a value that gives me the true number of rotations that will reach the end result for example k equal 7 is actually the exact same thing as k equals 2 if I do seven rotations or two rotations I'm actually going to get the exact same result if I wanted to I could verify that by walking through all of the rotations but that's very obvious to me and I know from the example they gave me that that's going to happen so this tells me that the first thing I probably want to do is I want to simplify this K value down so rather than having seven I need to get the length of this length list which in this case is five we can see that easily or visually and I'm just going to take the length I'm going to take K and I'm going to perform a modulus I'm going to say k mod length is equal to the true K or the real number of rotations that I actually need to perform in this case 7 mod 5 is equal to two and really the true K value that I'm going to use here is two so that's the first part of the algorithm that I figured out is I'm going to take part of my input and I'm going to simplify it to make my life easier so at this point I would start kind of writing down what I know even though we haven't solve the problem yet we know kind of the first step so let's write that down okay so Step One is written down simplify K and this involves taking K and just modulus by the length now actually when I write this I realize that in order for me to do this I need to know the length of the linked list and even though I can see it visually when I just write one out when we're given the linked list in our problem we're just given the head node we don't actually know what the length is so really the first step actually is to figure out what the length of the length list is so that we can simplify K so now that means I need to change this a little bit and rather than step one being to simplify K that's actually going to be step two step one will be to find the length of the linked list so we can do the simplification so now I've written my revised steps I'm going to start by finding the length I'm going to simplify the K value and then intuitively well I need to rotate the list now we don't know what's involved in doing that yet but we do know that will be step three and we're starting to work our way towards an algorithm so you can see how we're kind of breaking the problem down slowly solving small components of it and it makes it easier for our brain to kind of handle piece by piece we look at an observation we solve a small part we figure out one step of the algorithm we don't need to solve the entire thing at once in fact it's very difficult to do that you want to try to do it piece by piece so now we're at the rotation step so let's say we have our true K value right and we have maybe a simple length list like 1 2 3 for example purposes let's say our true K value is two meaning it could have been something larger but we simplified it down now what we need to do is actually perform the rotation now we want to start by kind of assumptions or facts that we no now with the linked list we know that this is singular what that means is that when I'm on some node here I don't have access to the parent node I only have access to the next node so I need to be careful in terms of how I'm storing these nodes and actually if I'm doing a rotation where I'm moving an element from the back to the front or from the front to the back what that is going to involve is me knowing both the tail and the head node so I know right away when I start solving this that I need to have reference to the head which is right here and to the tail which is right here I also know that as I perform these rotations The Head and the tail node is going to change because as I move elements to the front or to the back well we're going to have a new head and intuitively a new tail so we probably want to create some variables where we're storing the head and we're storing the tail so let me just kind of write some variables here I don't know if this is going to work but I'm going to start walking through this and see if I can come to a solution so I'm going to say head is equal to 1 and I'm going to say tail is equal to node 3 okay so I'm just kind of marking them down here so that we have them tracked now let's say I just want to rotate one element that's probably what we want to start by doing rather than rotating two let's figure out how we just rotate a single element and then we could just repeat that process as many times as we need to so if I want to rotate three to the front again we need a reference to the head and we need a reference to the tail so how do I do this well I need to two take three I need to move this to the front and to do that the first thing I can do is I can set the next pointer on three to go to one okay so that's good we can kind of say tail. next is going to be equal to the head and then I need to take maybe the next node so this pointer here and I need to remove this if I do that now three has really come to the front three is pointing to one and one is pointing to two the issue that I'm having immediately though is that if I just have a reference to the tail and I just have a reference to the head I don't actually have access to this Noe so how am I going to adjust the pointer behind to be equal to this next note so that tells me that this approach probably isn't going to work and I need to go with some other approach and find a better solution again to some of you what I just did may not have made sense that's fine it's me walking through and trying to understand how I can approach this and going through different Avenues until I find the correct approach I realize now that in order for me to do the rotation I need to have access to the previous node so there may be a different way that I need to go about doing this so what we can say here is that rather than maybe taking the back nodes and moving them to the front we could maybe take the front nodes and move them to the back now this solves our problem because if I have a front Noe and I move this to be behind three for example well I have access to the next node from the front node and from three I have access to its next pointer so I'm able to actually manipulate the two pointers I need to now what this is telling me is that rather than rotating the back elements I'm going to rotate the front elements but when I rotate the front elements my solution is going to look a little bit different so just look right when we have k equals 2 the official solution should be 3 2 and 1 okay so we have 1 2 3 goes to 3 2 1 so if we were going to rotate the back elements to the front then yes K is equal to two we need to do two rotations but if we instead decide that we're going to take the front element and we're just going to remove move the front elements to the back the required amount actually K can just be equal to one because I just need to take one front element and move it to the back I know it seems a bit weird let me walk you through another example so I have an example on my screen and we'll start going through it now we started with K = 1 but we actually convert that to K = 3 because we know we're actually going to shift elements from the front to the back so let's look at how we do a rotation one time now in order to rotate one to the back we simply take whatever the tail is and we point its next node to one so now we have what's known as a circular length list where the tail Noe is pointed to the Head node now if we're only rotating one time we could just remove this pointer and now we have a rotated list and we would have 2 3 4 and then one however that's not actually what we want we need to to do this three times so really we want to have four 1 2 3 so how do we know how to do that well once I do this and I go four equal to 1 The Next Step would be just to repeat this process but now we need to adjust our head and our tail notes so really we're saying okay tail. next is equal to the head that's the first thing we do when we want to rotate something but now that we've done that our head and our tail nodes have kind of changed right now our new tail node is actually equal to one and our new head node is actually equal to two right this would be the head now we're going to leave this pointer because we actually don't need to remove it but we know that this now is the new head and this now is the new tail so now we can just really repeat this process and we can keep doing this three times okay so if we repeat the process we say the tail do next is equal to the Head well we already have that connection okay so that's made and then we just need to update The Head and the tail okay so let's go ahead and do that so we can say now the new tail would be two and the new head would be three we can do the same thing again okay so this now is our tail this is our head so we're going to say the tail dox is equal to the Head okay so again that that's already done we don't really need to do that and then we can adjust the head and the tail okay so as we adjust the head and the tail we now have the head is equal to 4 and the tail is equal to 3 okay now we're done the rotation cuz we we've done this three times right head is four which is what we want tail is three which is what we want all we need to do now is we need to remove this link between the head and the tail so I can remove this link now we have four 1 2 3 so the reason I just showed you that is that actually all we need to do to solve this problem and it seems stupidly easy is we just need to take whatever the tail Noe is we need to connect that to the Head node and then we just need to go and find whatever the kith node is in our linked list and just disconnect its next pointer that's actually the entire thing we need to do so again we begin we take whatever the current tail is we connect this next to the head all these links will remain and then we just go and find whatever the K node is and just disconnect this next pointer and point it to null so when K is three third node gets disconnected when K is 2 second node gets disconnected when K is one first node gets disconnected that's all we need that solves our problem okay so in my horrible handwriting I just wrote this out we find the length we simplify the K value we perform the rotation the rotation involves taking the tail. next simply pointing that to the Head value and then we disconnect the kith node and we're done that's actually all we need to do there's a few other small steps in between for example to find the length we need to know how to iterate through a linked list we're going to assume we know how to do that to simplify K there's a little bit of math again we can write that in in the code to do the rotation we need to find the tail node and find the head node pretty easy to do we should be able to do that without having to write out a complicated algorithm and then disconnecting the kith node well that just involves going through again and finding the kith node so we're just iterating through the length list 1 2 three four oh four okay disconnect that's it that's all we need to do so now what I want to do is go over to the computer and show you how it would code this out and again as I code it out I'll explain how I'm kind of coming up with that solution step by step but really this is the easy part now because we know what to do we've written it out we've diagrammed it we've visualized it we have a good in-depth understanding of not only the problem but the solution we're going to implement and now we just need to go to the code and write some kind of translation of this algorithm so I'm back on the computer now and we're going to start coding this out now step one was to find the length so let's find the length of this link list now to find the length we can do the following we can say length is equal to zero we can then Define a current node which will be equal to the head and we're going to say while the current. next is not none then what we're going to do is say length plus plus or plus equals 1 because I'm writing this in Python 3 and then we're going to say the current is equal to the current. next I'm not really going to
explain this this is a very simple traversal of a linked list which most of you should know if you're going into these type of coding interviews now right away when I look at this I realize there's a potential for an error in my code the error is right here current as we see could potentially be none it may not be one of the list nodes to find here so before I can do this I just need to make sure that the head node is not none so I'm going to say if head is none then I'll just return that head because if there's no nodes in the linked list it doesn't matter what K is there's no rotation that we can perform okay so now we should have the length equals zero current equals head well the current next is not none length plus equals 1 current equals current. next now what this actually does for us is at the end of this iteration we have access to the tail note the reason for that is when current. next is equal to none that means that we have the tail because there's no more pointers there's no more nodes in the list so not only has this found the length but it's also actually located the tail node for us which is important because we need that for the next step so once we find the length the next step is to simplify the K value so we're going to say our true K is equal to and we're going to perform our simplification now the first simplification is to take K and to modulus this by the length of our link list however remember that actually what we want to do is we want to kind of flip K around and we want to do that by taking the length and subtracting that from K so if we have a length of five and K is equal to 1 then we actually want to take the four elements from the front and move that to the back as opposed to taking the one element from the back and moving it to the front again it's effectively the same thing but the way that we are going to solve this problem is important so what we're going to do is we're going to put these in parenthesis and we're going to take the length and we're going to subtract that from K mod length that's going to give us the true K value or the number of rotations that we're going from the front to the back because we've flipped the order now that we have the true K value it's time to perform the rotation so remember that the first step is to Simply take the tail node and connect it to the head node however before I do that I'm kind of realizing that if we have a node or we have a linked list so we have length one this could potentially be problematic because we could be connecting the head node to itself and creating this kind of circular infinite list which we obviously don't want so what I'm going to do is just do a quick Edge case check here something you should always be considering when you're solving these problems and I'm going to say hey if the length is one it doesn't matter what K is again don't need to do any rotation so let's just return whatever the head is of this length list so I'm going to say if length is equal to one then just return the head just to make sure I'm not going to run into an issue here uh with a potential Edge case of length one so I'm kind of handle the edge case length zero length one these are typically the ones you want to consider where you have nothing or you just have one element so now that's handled now we can go and do the real rotations so remember we're connecting the tail to the head so we're just going to say the tail Dot next is going to be equal to the head but actually that reminds me we don't actually have the tail stored in a ver in a variable so what I'm going to do is instead I'm going to say current because this really is the head node next is equal to the head which was passed in okay now we're just going to go and iterate through the link list starting at the head and we're just going to remove the nth elements next pointer okay so to do that we're just going to say four and we can say actually we're going to use a w loop we're going to say current is equal to the Head we're going to say w and we need some kind of count here so maybe we're going to go with the for loop we're going to say 4 I in range and this is going to be let's go with the truecore K and we're going to say current is equal to current. next okay so now what's going to happen is we're going to go and we're going to find that k element and then we're just going to remove that pointer so I'm just going to say current. next is equal to none so I remove that kind of circular aspect I'm just getting rid of that one pointer that we don't need so before I run this code or before I would like submit this to my interviewer I just walk through it and make sure I don't have any mistakes totally fine if you do have a few mistakes by the way and that's normal especially if you're coding this out on a whiteboard but you do want to just do kind of a quick check just see if this makes sense so if the head is none okay so if that's none we're returning the head makes sense Define the length Define current okay we're going to say while current is not none length plus equals one current equals current. next okay itating through the length list if the length is one return the head makes sense true K value is equal to length minus K mod length Okay current next equals head so we're connecting that tail node which we have to the Head okay I think that makes sense current is equal to the head because we're now going to ITR through again for I in range true K because we need to find the K element good current equals current next so just iterating and then current.
next equals none and then lastly return uh actually the new head note so this is the one thing that we're going to need to kind of have here is we need to know what the new head note is which I kind of missed so let's kind of go back in here and figure out how we would get that so if we're saying here that current. next is equal to none we're trying to disconnect the tail from the head which means current. next is the head so what we can do is say head is equal to current. next before we disconnect it and then when we disconnect it we still have access to the head and then we should be good so let's go for a sanity check here and let's run this uh and just see where is the Run button okay run up here okay so I just ran this code here and I realize that we have a small mistake that we need to fix so the first mistake here is with the length it says zero when actually we need to start the length that one the reason for this is that we're already accounting for the head in the fact that we say while current. next is not none because we're assuming that we have at least one node so we should start with the length equal to one now we also have a mistake here in this for Loop where I say 4 I and range true K I need to actually subtract one from True K and the reason for that is we've actually handled one of the rotations already by saying current. next is equal to the head so when I do this I'm rotating one too many times because I've already done one of the rotations with this manual line that we've written so that's kind of the change that we need to do here um that should hopefully fix this for us now there's maybe a more elegant way to write this solution keep in mind I'm doing this live in front of you I haven't seen this problem before so this is what happens right when when you're solving coding problems anyways let's run this now and hopefully this will work and there you go now we have case one and case two accepted now that doesn't mean that the solution is perfect yet what we can do now is we can submit this and uh let's see what our results are and if this actually passes all of the leak Code test cases okay so there we go we actually submitted this it was accepted it passed all of the different test cases and you can see that our runtime beat 76% of people I don't know if that's good or not uh we probably could have done better and improved the space and time complexity here just a little bit but overall I think this is a decent solution and hopefully kind of fulfilled the purpose of this video so there you go guys I'm going to wrap up the video here I hope you enjoyed and found this helpful if you did make sure you leave a like subscribe to the channel and I will see you in the next one [Music]
2024-07-25 15:18
