Memoize - Leetcode 2623 - JavaScript 30-Day Challenge

Key Takeaways

hey everyone welcome back and let's write some more neat code today so today let's solve day nine of the JavaScript challenge memo whoever said dynamic programming wouldn't come in handy and this is probably my favorite one of the challenge so far a lot we can learn here it's similar to the last problem where we have a wrapper function for our inner function over here and we only want this function that we pass in as a parameter we will pass this in we only want it to be executed a single time at least with the exact same parameter so here let's take a look at the example we're calling memo passing in this function that just adds two numbers together and returns them the first time we call it it returns five the second time we call it it also returns five but actually the second time we called it the function at least this part did not execute this entire part and we know that because our call count variable was only incremented a single time so that's kind of the behavior we want to add and I think the editorial in this problem is really good so quickly let's skim through that before we solve the problem first they tell us that this is memoization which is really just a fancy word for caching we are caching the result of sub problems so that we don't have to repeat work of course this is a technique applied in dynamic programming if you're familiar with that but it's a technique that's used in other places as well firstly they make a quick mention of pure functions which are just functions that given the same input will always return the same output well well adding two numbers is definitely a pure function but what's not a pure function is getting the current date at any given point in time if we get the date right now it's roughly 6:00 p.m. where I'm at but if we get the date an hour later it might be 7 P.M clearly this is not a pure function so it doesn't make any sense to apply caching to a non-pure function but technically we still do sometimes apply caching to non-pure functions like sometimes your browser will cach certain images and things like that even though that data is stale and you know sometimes this can create buggy Behavior that's kind of why the first thing you'll want to do when you have issues with your browser is clear your cache but let's continue skimming they mention exactly that that caching website files like images JavaScript files CSS things like that react components are also an example of pure functions I wouldn't know because I use angular a grown man's framework just kidding I really hate it but the reason react uses pure functions is that they create a good level of abstraction you don't really have to understand a lot about the inner workings of a component you can expect that given the same input it will return the same template which will then be rendered to the user caching API calls is another common example just like caching images of course sometimes reading from a database can be expensive so sometimes you create a copy of that data and put it in something like reddis which is usually in memory and finally we arrive at dynamic programming yes recursive dynamic programming does make use of caching or memoization and continuing this is the part I probably won't talk about today because I expect that we will solve memo too where we can probably discuss this stuff further so now let's finally actually get into the solution of the problem it's going to be similar to yesterday where we do have this wrapper function and the purpose of this wrapper function is that we can actually add state to this inner function we are creating a function that we're going to pass into memo just like in this example down here maybe our function adds two numbers together but for us to know that this function has already been called we need to have some type of state that we maintain within memo so that state in our case I'm going to call it a cache and it's going to be const because it's actually going to be an object because remember we are not only storing the result of one function call we might call our function with two and three but we might also call it with two and seven every un unque parameter that we pass in we want to Cache the result of it so we don't have to recompute it in the future so in this case an object AKA a hashmap is going to be used for that in JavaScript so then in our inner function that we're going to return of course we want to call our FN function given whatever arguments we pass in they could be an arbitrary number of arguments remember this dot dot dot is important because not only could we pass two and three but we could pass in 2 three and seven or eight it allows us to pass in an arbitrary number of parameters that's the significance of the dot dot dot so we call our function with these parameters but we only want to call this function if we haven't called it before how do we know if we've called it before if the result is already stored in our cache so how do we check that do we just use these arguments as a key in our Cache can we just say is args in Cache no we can't just do this because args here is an array which is an object which generally can't be the key of a hashmap pretty much we can only use strings or numbers but args is always an array so what we do before we use this is we have to convert this into a string that we can use as the key for our hashmap so we say key is equal to json. stringify this args object json. stringify takes an object which in this case an array is also an object and converts it into a string which then we can use as a key in our hashmap so we check is this key already inserted in our cache if it is we can simply say return the cach using this key if it's not then we would have to compute it like this cach equals Key Well equals the function return value and then we return cache with this key inserted and that's pretty much the entire code let me quickly run it to make sure that it works and as you can see yes it does but I'm not quite done yet there are a couple important things to mention firstly we've been using this pattern a lot lately and I'm actually surprised that our code worked even though I had this uncommented so I'll go ahead and comment it the idea here is that we have this wrapper function that is going to add content or add functionality to whatever inner function that we pass in and in this case it's very general all it's doing is caching the result of dysfunction this is an example of The Decorator design pattern or at least it's reminiscent of it because technically this is an objectoriented design pattern but clearly here you can see we don't really have objectoriented programming going on at least not in the traditional sense but it's very reminiscent of objectoriented programming given the fact that we do have some hidden State here so I wanted to mention that because a lot of people think they don't know any design patterns but if you've been solving problems with me you've actually been learning them as you've been going and lastly if this dot dot dot ARG stuff doesn't make 100% sense to you how did we convert an object into a string and especially how can we be sure that this string is going to be unique just like the parameters well let me quickly prove it to you suppose I have a function f which accepts an arbitrary number of args the power remember of this function is we could call it with a one we could call it with a one two we could call it with a 1 two 3 any of those would be valid but what happens now when I take this args which is an array remember and stringify it what is it going to look like well let's console log it and find out so now I'm going to run this and you can see it's 123 which is kind of what we expect args is an array and once you convert it to a string I guess this is what it's going to look like this string 1 2 3 and closing brace or bracket so we pretty much can be sure that if we pass in a unique combination of parameters we will get a unique key at least in the case where our parameters are integers which I believe they mentioned in the problem that we are guaranteed that our inner function will be called only with integ that's all I had thank you for watching if you found this helpful please like And subscribe if you're preparing for coding interviews check out NE code. it has a ton of free resources to help you prepare thanks for watching and I'll see you soon