Two Sum Algorithm in Javascript

hello alright so real quick we're gonna do the to some algorithm which is what these Fang companies want like one of the main hours they use to test coding competency and programmatic knowledge of kind of you know you're trying to get in a nice job you're probably gonna know how to do some stuff like this you're gonna have to know how to do some stuff like this so the reason that this to some algorithm is good is because you can refactor it a bunch there's many different ways to do it you can use dynamic programming in it so it's it's you know it's pretty good so we'll go through as though this were a coding interview right so I just have a blank blank vs code template right here so I'm gonna make a couple of files real quick so I'll touch some CAS you'll see why I'm putting any capital later and then runner is going to be s code so now we'll just open this up the to some algorithm basically gives you an array let's just say 1 2 3 4 & 5 and it gives you a sum let's say 9 so so what it wants you to do is return any two numbers in here that that add up to 9 right so we can see that 4 & 5 add up tonight so we should return an array of 4 & 5 that's what our array should that's what our function should return if there isn't numbers like if the Sun was 99 it should return something you know like not found or something like that right so um the first way that we'll do it we'll do it in brute force and that'll be an O N squared time complexity or quadratic time this is the wrong way but it it'll show that you know how to refactor code and stuff so let's say that I'm given that problem hey we're gonna give you an array we're gonna give you a sum to look for you return the two numbers that add up to the sum or you return not found in your function okay so let's make a function we'll call it to some and like we said earlier it's gonna take in an array in a sum right and let's go ahead and define those so cons R is going to equal an array with one two three four five six seven eight nine and then Kant's son is gonna equal what's nine and eight seventeen let's just say 17 okay so what we want to do in this brute force approach you might think well how can I solve this basically I can have like an an eye here and a J here and I can say is one plus two equal to 17 which is what we're looking for no it's not I'll increment J one plus three no one plus for node 1 plus five note one plus six note one plus 7 over 1 plus 8 no 1 plus 9 no I'll increment I to here so two plus three note increment J 2 plus 4 note 2 plus 5 no 2 plus 6 no keep Lissa so you can see it's a lot of calculations and if the answer we're looking for is here and the array that were lifting through is like you know 500 characters 500,000 characters long this is the incorrect way to solve it but it still will work one telltale sign that are you using wrong thing in programming for the most part is when you have nested for-loops that's a big no-no I can't not friggin tight all right so to get this kind of functionality we would have to use nested for loop so let's go let I equals 0 I less than r dot length I plus plus and then within that we'll get our J so for let J equals 0 J less than our data length J plus plus actually we don't want to start J at 0 we want to start J 1 increment more than 1 so we'll just put it at 1 so that should work just the same so I will start here at 1 J will start here then J will increment then once it gets the end I will increment to here and then J will go here right ok so that's the way that our algorithm is gonna run and we'll go if R and I is what we're checking for if RI + rj if that ever equals the song that's passed in then what we want to do is just return an array with our and I and RJ as the elements within it if that doesn't happen we want return something like not found okay so what we can do as a teaching tool is right here at the top we can go let count you don't have to do this but I'm gonna do it let count equals zero and then each time we run through this for loop we'll just go count plus plus so we can see how many times if it doesn't return we can see how many times count has been incremented how many you have calculations have happened so CLG you count right down here okay so let's run through this where we're going through we're looking for 17 let's see if it finds it so node sums Jas and it didn't find it because we didn't call the function so let's see LG to sum with the are and some passed in and let's run it again so we get eight and nine which is 17 so now let's see when it doesn't work like 177 will not be found in this so let's see how many calculations it does to show that it doesn't work so it did 72 calculations on a nine number array to find that the 177 wasn't in there so that's the most amount of calculations that we'll do just to give you a negative response so that that's a lot of calculation that's pretty expensive because we only got nine elements in here imagine if you had you know 250 thousand or a million or something like that so what you want to do is you want now we want to write it in not the brute force way we want to refactor to where we can get a linear time or an O of n time complexity what oav n means is that the total number of calculations to get a negative value to get a negative response like return not found will only be the amount of it will be directly proportional to the amount of elements within the given array so o of n whereas n is the length of the array the length of the array here is nine there's nine elements in it so this function that we're about to write at most should do nine calculations and that's it we'll never do more than that that's what we're shooting for so let's go to some right here and this is the this is the linear time or not letting your time the right way and olivine is in here okay so here we go to some equals and let's get rid of this stuff to some it's gonna take in again it's gonna take in an array in a sum and this is you know this is basically dynamic programming we're gonna break this into smaller parts to solve a larger problem up here since we're constantly doing a comparison between two indexes we're doing it are and I and J and are at J well right here what we could do is let's go Const result or constable stall that passed numbers equals an empty array then we do our for loop so for left I equals 0 I less than r dot length I plus plus let's do it like that and then in here let's go let current equal R and I that'll be the current number we recommending through and let's let needed number equal sum minus RN I and let me explain what this is so let's say that where our current number is 3 and we're looking our son that we're looking for 17 and the current number we're on it's 317 minus 3 is 14 so we can check this passed numbers array and see if 14 is in here if it is not we can pass this 3 in and then check it later if we run across a 14 it'll find this 3 in there and then you could you can return those so the way that we write that will say if not needed or passed numbers Don includes needed number if it doesn't include it then we're gonna pass into it so passed numbers dot push current will push the current yet if it is there so this would be the else statement we'll just return an array with needed number and current and if that doesn't work we'll just return not found so let's run this and let's see if it works we have the same we're gonna have to we're gonna have to comment this out because the the functions are named the same so we'll move this down here okay so let's run it again let's go to node see if it works and it gives us eight nine which is it which is what we wanted now let's give it let's do that same thing we did in the first one where we put a count in here so let's count equals zero and then each time it runs through this we're gonna want to increment count by one and then here if it doesn't find it we'll just consult log count and we'll see how many counts we get to get something to get a no answer in here 177 will not be in here so let's see how many calculations it does see right here to get this not found here it only did nine calculations which is in so oh of in it ran in calculation so that's as many as it's gonna run even if it failed even if its finds a even if it returns a not found it's only gonna run those so this is the proper way to do it this is the right this is the right solution you can talk about the dynamic programming that you did while bringing in another array and check in those pasture-raised you can talk about the time complexity of it and blah blah blah so now another good thing to do would be well what if they say something like well we want this to be like so module modular code that you can pass around we want to be able to export this to another file and run it which is you know what you do in the real world so here we can just do a class so let's put it in a class so a function that's globally scoped is just a function but as soon as you attach that function to a class it becomes a method so this to some will become a class method for or let's take a class fold of sums because that's what we named it up top class sums and let's put this method now this former function now method in the class and we can take off this Const keyword upfront because on class-based methods you don't you don't need that but what a class does mean every time is a constructor function so go constructor and here we're not we're not we're not doing anything with it so we're just making it you have to have this line usually this is where you would add in arguments that when you're creating an instance so let's say that I was making a node class or something and each node had a bit of data you would pass in the data in the constructor so like data and then you would go this data equals data that's passed in that's that's for another video of class base video but just know that you have to have this constructor keyword right here so let's say that I wanted to export this this class which contains the to some method on it so I could go this is common jeaious this isn't the es6 syntax like you would use the the export statements that you would use and reactor some newer front-end framework that has webpack and babel implemented in it this is just common jeaious this is more like you would find a node for example so you can just go module exports equals sums because that's our class so now that we're exporting that we go to another file here we can just go const will import it so const sums equals require this is how you import dot slash sums so that's our relative path to it and that's what we put in quotes right here so now we have access to it on this variable called sums so we can go come on sum equals new sums in boat so now we should have access to that to some method that we wrote so we can just console.log right here some dot two sums with the do we have the array yeah oh I erased it okay but over here you could just make a new array which do we put a thirsty array or some array so we can go cost array equals same thing one two three four five six seven eight nine Const sum equals well we don't want to call it some we'll call it number equals we won't want to call it sum because we call our instance some class some so we don't have naming conflicts so the number that we're looking for we'll just call it number we are looking for that's really bad way to name that never do that let's just do it eight nine against that seventeen so right here we'll put I don't want to name it never we're looking for that's too long but number let's button um so but I want you to understand that you can call it anything that you want the only reason I'm not calling it some is because I called this instance of the some class some so we don't want to we don't want to run into each other with naming conflicts so in our method you can see that we bring in the array first and then the sum second so we'll just go right here we'll just go our and numb and we're running this sum dot to string some is a instance of the some class songs class so let's see if this org we're this time of run runner duck yeah so no runner and it gives us eight nine cool so it gives us the same thing so let's try it 175 this should return not found and it's still returning this nine because right here we have this count let's take this out because we were just doing that to show so let's take sounds running again and it's showing it gives not found so what we've done here is we've refactored a function two different ways open or quadratic time and then o of n squared which is quadratic time which is the wrong way which is this and then Oliv in time or linear time here and this then we put it within a class called sums and we exported that class to a runner file that this is where we actually had access to those we had to create a new instance of the sums class called sum and then on that some instance we ran the method to some see if we try to just do to sum like this we would get this error see console dot log to some art to sum is not defined because it's looking for to some like it was right here like like pots to some that's what it's looking for so you have to let it know where it is so it's on the some instance that we created right here okay cool so that's all pretty good and Deontay Wilder and Tyson Fury about the fight so I'm gonna watch that y'all take it easy

Channel: Adam Coder

Views: 757

Rating: 5 out of 5

Keywords:

Id: NrDb_biSCgg

Length: 15min 27sec (927 seconds)

Published: Sun Mar 15 2020