Transcripts
1. Introduction: My name is Sarnoff, and I'm a full stack software engineer and engineering instructor. I've told software Engineering at a coding boot camp, and something I noticed repeatedly was that are graduating Students, although extremely bright and capable of building powerful, dynamic websites, were not ready for the types of questions they saw in their interviews. After watching these students struggle with typical interview questions, I decided to create and collect questions that students might see in their interviews. And I handed them out. Was extra practice for the students to try. They repeatedly told me how much the problems helped them see the holes in their knowledge and fell them with the skills they needed. This course is the culmination of those questions. Almost all of these problems are variations on questions that I myself have been asked, or that others I know have been asked in interviews. Well, you won't see these exact questions in your interviews. The strategies you learn by solving them our public are applicable across almost every problem you'll be given. Here's the general structure of the course typically will start by creating a brute force algorithm that solves the problem well, then refine it until we can optimize time or space complexity or both. By the end of the course, you'll have mastered several algorithmic strategies that you can apply toe a wide range of problems. We'll learn ways to critically analyze the algorithms we come up with and to find, turn them to reduce the amount of time they take. This is exactly what an interviewer is looking for. There are a couple of requirements for this course. Um, first, you should have a basic working knowledge of JavaScript and the ability to write meaningful code with it. You should also be familiar with Basic ES 2015 concepts, such a zero functions and the keywords Let and Const. You should have some idea of what the terms, time and space complexity mean. It's okay if you don't know exactly what they are, since we'll walk through finding them in detail for every solution. The code editor that I use in my videos is Ripple. Uh, you can get there by going to rebel dot i t slash languages slash javascript, and the reason I use this is because it's simple and functional, and let's you focus on your code, but you're of course, free to use any code editor you like. The project for this course is to pick any one of the problems covered in the class. There are a total of five listed here and share your own solution. There are 1000 ways to solve any of these problems and the class will benefit from seeing your version. Welcome to the course. I'm excited to teach you what I know and to help you ace your interviews. Whenever you're ready, I'll see you at the first problem.
2. Array Subsets: The next problem is a ray subset for this problem. Our function is going to receive two arguments which are both going to be a raise, and these arrays will only contain numbers and strings. Our goal is to find out if the second array is a subset of the first are a and what that means is we want to return. True. If every item in the second array is also found in the 1st 3 we have a couple hints here. As usual, This problem has a few different solutions with different time complexities, and we'll go ahead and cover all of them. And one of the keys to this problem is how to deal with the repeats when an item is present two or three times. Here are some examples for this 1st 1 The same items are present in both a raise, the same exact items just in a different order. So we know that the second is a subset of the first in the next one Thesis and Array has 12 and three, and the first Array has an extra one, so it's still satisfies our conditions in the next one. The second array has a three which the first array doesn't. So we want this. We want our function to return False. For this case and the next one, we have an extra two. So again false and then the 3rd 1 Although the items, the number of items is the same, thes three items do not appear in the first rate. Only one off the ones does. So again, we want false return. Try the problem and go ahead and press play when you've at least attempted it. Let's get started. So, as usual, we're going to need a loop. But which way do we want? A loop over. Well, we want to make sure every item in the second array is present in the first. So all we really care about is every item in the secondary. The 1st 1 might have a few extras that we don't care about. For example, this one. So it seems like it would be a better idea to loop over the 2nd 1 And what do we want to do in here? Well, whatever item we're currently at, we want to look for it in the first array in the super set. So here we're just using the index of method to find where in the super set this item exists. If it exists ill. If it doesn't, then Super Index will be equal to negative one and we can immediately return false. What this means is there's an item in the second array, not in the 1st 1 so we know that it can't. The 2nd 1 can't possibly be a subset, so we can immediately return false and at the end of the function. And if everything goes well, we want to return true. Let's go ahead and test this function out and we don't get quite what we expect these to work. This one works to. We get to truce of false and then two truths. So these two conditions are failing. Let's take a look at this one. Well, one easy condition we can figure out right away is that a subset has to be smaller than or equal to the size of its super set. So if the subsidies ever bigger, then we know it can't possibly be a true subset. So let's go ahead and about it. It's running again and this was passing. We'll get a false here, but we still need to make this piece pass right here, and there's no easy way to get around that. So our function here is almost complete. But there's one important thing we need to do, and that is. Keep track of the number of each item that appears, and we'll do that in the next lesson.
3. Double Array Algorithms - Diving Deep: Welcome back to array subset. We're almost done with our function. All we need to do is make this case right here fail at the moment. It passes the test and we get true coming back from our function. What we need is false coming back because this array is not a subset of this array. How can we do that? Well, at the moment, what are loop is doing is it's going through this second array and its processing each item the first time it sees this one. It looks for it in this array and it says it's there. It finds it great. It continues on in the loop and gets to the next one again. It looks forward in the first Array and it finds it and finds the exact same one. And it says, OK, we're good to go and it does that one more time. We need to tell it that it can't look at this item this twice and can't look at the same item multiple times. If if an item shows up more than once in the subset, it has to show up at least that number of times in the super set Well, one thing we can dio, it's simply delete the items we find in the super set that would solve the problem. For example, what is the function looks for this one and it finds it here upon finding it. We can just delete it from the array. The next time it looks from it, it looks for the one it won't find it there and will return false. So let's go ahead and code that in first we don't want to directly modify this array were given, So let's make a copy of it. Sorry, Super copy. And with the spread operator, this is all we need to do to make a copy of this first array. And let's try running this again and all our tests pass this functional work. Let's go ahead and look at the time and space complexities. So for time, we're going to call this M, and to this end, we actually have two different variables. So we need to keep our time complexity in terms of both of these variables. Here we have and all of em. Ah, we have a no of em process copying an array takes what we have to do is have toe loop through the array and copy each individual item. So this is a linear operation right here in this loop, we start out with over N for secondary and here we're actually we have another loop has mentioned in a previous problem. Index of is a loop and we're looping over super, which in our case, is M So we haven't o of m here because they're in a loop. We multiply them together and we get all of em times n and because O of m times n is a factor greater than this one we can after. Go ahead and ignore this because it's inconsequential for the space complexity. We create a new array by copying the original. So it's going to be o of M. There's a different way to solve this, and it will actually improve our time complexity a little bit. Let's go ahead and work on that. So instead of operating like this, where we are looping through the subset and then trying to find it than the super set were stood going toe loop through each one separately and keep count so we can keep this top, we won't need any of this anymore and will keep the return true at the bottom. So we've employed this strategy previously, but what we're gonna do is create an object to keep track of these numbers. I'm just gonna label this cattle. So what we're doing is we're first looping through the super set and building up this object by the time we're done, What we want this object to have is a representation of every item that's in here, meaning correct counts. - So this is the case. The CIF statement is the case in which were coming across a string or number for the first time. So if it's the first time, we want to give it a value of one. If we've seen it before, we just want to increment it, okay? And that's all we want to deal with this loop. This loop will contain a correct count of all of the items in here. And let's just lock that out to make sure, and we'll go ahead and try it with just two. This last item here. So we're running this example right here, and we're looping through this array and that looks correct. We see one appearing ones to appearing once and three appearing once and just to make absolutely sure. Let's add another three. Then run it again and we see three twice. So this looks like it's working. Fine. Let's go ahead and loop through the second array. - So here we're processing an item in our subset, and we're trying to make sure that it's found in our account object. If we haven't seen it before, meaning this is undefined. We know that we have something president, the subset that we don't have in the super set. Because if we did, it would have been stored in this object by this loop. So if this is the case right here, we can go ahead and return false. However, if it's not undefined, we just want to decrease its value by one. So this will decrease our account. What happens? One. The number gets to zero. What we're doing here is if the Count reaches zero, we're deleting the item entirely from our object from count. That way, if we process that item again, we'll go through this loop and will enter this case. What that means is we've come across this item more times in the subset than we have in the super set, which means it's not a truce upset, and we can return false. Try to try to wrap your head around that. Let's go ahead and log count again just to make sure it's working fine at the end of the second loop. So we expect to see, let's see, uh, we see false because it's returning false. Okay, let's change this a little bit and make it 123 So what we should see is an empty object. And that's exactly what we do. See, because this loop processed disarray and this loop processed disarray, they essentially cancelled each other out. Items were added and account and then removed by this loop right here. So we should see nothing coming out, and this looks like it's working the way we expect. Let's go ahead and run these and see if our function is working correctly and we still get a true over here. Why is that? Uh, didn't change this back and it's working exactly as we expect. Let's look at the time complexity for this one. So we have an O of in this case we're going to the super sets, all of em. And nothing in here is a loop. And here we have an O of N. Then nothing in here is a loop. So this time, because thes loops are after one another and we don't have one inside another one instead of multiplying. What we're gonna do is add these two together, so we get O of M plus n for space complexity. We are storing every item in the super set into this count object. So that's just going to stay o of M. So this solution works perfectly fine. And the next video we'll go ahead and figure out how to solve this problem if we're not given just strings and numbers in our arrays here. But we'll make this work for every type of input seeing the next lesson.
4. Array Subset: The Optimal Solution: welcome back in the last video, we managed to solve the array subset problem. Our solution is down here and it doesn't work for every example here. And it'll work for every example in which we use either numbers. This is a type of I apologize, I should say, or it'll work for any input in which we give it either numbers or strings. In this case, they're all numbers down here. But it would work if we replace them with strings just the same. And this is key. Our solution will only work for numbers and strings. If we try to use objects, a raise or functions are our function here is going to break down and let's go over. Why notice that we store all of our information in an object here? Objects are great, but they have a little shortcoming. And let's talk about what that is. - So all I have done here is create an object and then attempt to create 33 key value pairs, one with an object, one with a string and one with a number. And when we long object, this is what we get right here. This isn't the most helpful So let's actually log each item individually and we see these here, so that's working correctly. Let's also log instead of the valley here. Let's go ahead and log the type of the key and noticed that every single time we get string , this is the fly was talking about. Whenever we use brackets with an object to either set of variable or access something, what happens internally is that this item, whatever happens to be first, gets converted into a string. So this object right here gets converted into the string object object. And that just happens to be how this platform ripple decides to decides to use it. Others could simply call it a string with the word object in it. Or it could be something else. It could be even this string bracket bracket, but here it's object object, and it is indeed a string 25 also gets converted into a string. So rather than actually being the number 25 what goes in here is the string 25. Now, if we have multiple objects and we try to used both of them, let's see what happens. The problem is that these two, although their distinct objects. As we can see here, we clearly made two separate objects. They both get coerced into the same string object object right here. And that means one of them simply doesn't get inserted. Rather, we insert this and then this completely overrides it. Just to show you that that's happening, we get also an object. So this has been essentially removed from our object. Okay, we have that over with. Let's go ahead and discuss how to actually fix this. So instead of an object here, we're going to use something different. We're going to use an E S 2015 construct called a map. Now, a map is basically the same thing as an object except it. Instead of string defying its keys, it will keep them as they are. So it's an object that holds key value pairs, and any value may be used as a key, not just to string the use of just fairly simple. You can go ahead and read the documentation to learn the methods, but this example right here will give you everything you need to know about it. And as we use the methods will be talking about them anyway. So let's go ahead and dive right in. So instead of an object to create a map, we use new math to look for an item instead of checking. If it's undefined, we use a method called has and we don't need this. If the item is present in our map, this will return true. If not, it will be false. Instead of setting in instead of setting a key value pair of this way, we do it differently. We use set, and the first item we give it is going to be what we want to set, which will. Sorry, It's going to be the key we'd like to set. So that's going to be the current item. And then the number of we want to give it in this case one. We would have to change this as well. And what do we put a second value? Well, we want to set. We want to set it to whatever the current value is plus one. I just realized this has to have an exclamation point because what we're trying to do here is check and see. We're trying to make sure that our map does not have this item yet. If it doesn't have the item, we want to set its value to one. And if it does have the item, we want to increase it by one. So this is correct. Moving on to our second loop for this, we can actually replace it with this exactly as it is because we're trying to check the exact same thing. This right here can be replaced by this with a small change. So instead of adding one, as we're doing here, we want to subtract one. So to decrease this items count, we're getting its current value subtracting one and setting its new value to that number here, Instead of accessing this as we would with an object, we're just going to use the appropriate mountain method. And here we are using the method map, Doc delete and we simply want to pass in, oops, current item and this should hopefully work. We get the exact same values as we expect, so it looks like it's working. I encourage you to change these up and try them with objects, arrays, functions, strings and numbers all in the same example. This new function we have here should work for anything you give it. The time and space complexities remain the same. A map is basically equivalent to an object, just with this new added feature where the keys do not have to be strings. That's it. See you in the next video.
5. Maximum Profits through Brute Force: welcome to the next problem. Maximum profits for this problem. We're going to be given an array of numbers that represents the prices of a stock from the beginning of the day to the end of the day. For example, given this array here, the stock started at a price of 10 and ended at a day at a price of nine. And it went through these in order during that day and went through these prices. Our goal is to find the maximum profit possible by buying once and selling once in a single given day. So from this array, we want to find the maximum profit we can make. There is no shorting, meaning you must buy before you sell and if no profit can be made. For example, if the stock price just went down all day and this looked like 10 98765 Then instead of returning a negative number, we just want to return zero to indicate that no profit can possibly be made. Let's go ahead and get started as usual. We're going to need our four loop and what we want to do. We'll start out with the brute force strategy, which means calculating every possible every possible profit we can make and then returning the largest one we find. And let's think about how to do that. So if we bought it 10 and sold at seven, we are profit will be negative three. And we want to store that somewhere. If we saw if we bought it 10 and sold at five, our profit would be negative. Five bought it 10 and sold it eight. And on and on and on. We wouldn't make much money buying at 10. Destroy seven. So by its seven sell at five. Our prophet is negative to buy at seven. Cell at eight. Profits one by its seven Sell it 11 profits for starting to look good. We'll just go through this on and on and on until we get every single possible profit and then we'll return the highest one. So to do that noticed that when we started at 10 we then had to process each of these. When we started at seven, we had to profits each of these. So we're gonna need a loop inside this loop. I am forgetting what this loop is going to have here I think the same thing. Prices start length up. I see this has to be equal to a I plus one because we want to start after the position of and to store each of thes possible profits. We want to create an array. And in here, all we need to do is calculate the profit and put it in the array at the end, we want to return the maximum. So what we can do is use the function math dot max and math. Not Max takes in several numbers, as many as you want to give it, and it'll just returning the maximum number. So in here we can spread out our profits array. Ah, one thing I forgot in here we want to start this off with zero. So if again, if prices air just going down, going from, let's say, 928642 men, no matter where we buy the no matter where we sell our profit is going to be negative. Having this here, insurers that math dot max will a least get zero every single time. So that solves the condition we mentioned earlier. Where if no profit can be made we want to return. Zero. Let's go ahead and test this. We'll just use the Serie right here and we expect to see six looking good. Okay, let's talk about the time complexity in space complexity of this problem. So we have a loop that goes through our right and we have another loop that goes through not the whole already but part of theory. This is definitely going to be Oh, of End. And this one is also going to be oh, of n even though it's not going through the entire array. On average, this loop is actually going through half theory. For example, starting at 10 J is going to go through five numbers starting at seven. It's going to go through four, starting at five. It's going to go there three and then two and then one. The average of those numbers is half the length of this array, so this is technically and over two. But we drop constants so both 1/2 end becomes, oh, event. And because these loops are inside one another, we multiply. So we get O of n squared for space complexity. We're actually pushing this number of prices into our profits array. So this has to store every single thing that this Lou produces. So that is actually also going to be o of M squared. They're gonna be the same. We didn't talk about this one. And this is actually also going to be, oh of and squared because math on Max as a loop in itself, it has to search through the entire array and give us the largest number at finds. And the size of the array as mentioned, is over and squared. Or it's proportional thio of end squared. So this itself is going to be o n squared. And we would add this to the value we got from the loop and that gets us oh, of two and squared. And we always drop Constance. So this could just go away, leaving us with O of n squared, which is what we had initially. Anyway, we started out with over and squared and ended up there, so this essentially doesn't change anything for us. That was the brute force solution. And in the next video, we'll go over a much faster one
6. Maximum Profits: Intelligent Processing: in the last video, we solved this problem using a brute force solution. We're calculating every possible profit that can be made and just returning the maximum one . Let's go ahead and try this a different way. So let's think about what we could do to do this in a single pass. Let's try to get this to O off, and currently it's and squared, and we've managed to get her to over and a few times before. Let's see if we can do it this time. Well, how do you calculate a profit? You take a number and sorry, you take a number and then subtract a number before it. How do you get so using eight. How do we get the maximum possible profit from selling at eight? Well, we look to the ones to the left, and we'd find the lowest number we can. It's not 10. It's not seven. It is five. So the maximum profit we can make here is three. Looking at 11. How do we find out the best possible profit we can get from selling at 11? Well, that would be finding the large number in here. Sorry. The smallest number in here and selling. So selling at five, we can turn this into code if we just keep track Of the smallest number we've seen so far, we can. Then as we move along, subtract whatever number we find from that number. Let me show you what I mean. So we're just using two variables here to keep track of these two values throughout our loop men. Price we're going to assume is infinity and we'll update it as soon as we started. Loop and Max profit will assume zero and we'll update it whenever we have to. - We just make sure this works. It does. This is actually our whole solution. Let's walk through what we're doing again. We're assuming the minimum price starts at infinity. So we're saying just basically, insert an infinity right here in this loop. We're going to update that whenever we need Teoh. So as we're moving through this, we're going to update it. Infinity isn't actually here, so we're starting at 10. And we're saying the minimum price that we've come across so far is the lower of men price or the current price. So the lower of infinity or 10 it's obviously gonna be 10. So men prices now equalled. Attempt Max, profit is going to be the current number we're processing minus the minimum price we've seen so far. That's what follows our rule. We just keep track of these two throughout our loop and we update them whenever we need to . At the end, we have Max profit already stored in our variable and weaken. Just return that it really is the simple time and space. We've turned a double for loop into a single loop. And none of these operations take up a significant amount of time. They're not linear or anything higher there, just constant time operations. So they're not going to change it. And we're gonna CEO of an O of N time complexity First space. Let's see what we're storing. We're storing two variables here. And no matter how large this sorry is, we don't need to store any more data than these two variables. So this is after gonna drop down from N squared to one. This is the solution that would win the interviewer over. It's difficult and shows the ability to logically deal with numbers and time. It's elegant, short and sweet, and has the best time and space complexities imaginable for a problem like this again, Just by keeping track of a few numbers through her function and a little cleverness, we can bring down both our space and time complexities considerably I'll see in the next video.
7. Single Mutation: it's problem is going to be single mutation. We're going to write a function that will take in two strings, and we need to determine if the two strings are identical, except for possibly one mutation. There are three types of mutations, and those are relations insertions and substitution ins. A deletion is just the dilation of a single character and insertions. The insertion of a single character and a substitution is one character change, with the strings being the same length. In the end, go ahead and try it on your own and come back when you're ready. Let's go ahead and start this problem, so we want to start by writing loop. But what does this look good on? Look like? Well, at each step, we basically want to compare the exact same item and both strings. So as we go through this string, we want to compare the first character here to the first character here, the second character here to the second character here and so on and so forth. Let's see how we would do that. The key is actually using a different type of loop than we've seen so far. Well, it's still a for loop, but it's going to be structured a little differently. Let's go ahead and write the conditions down. Coma. This might seem like a strange loop, but it's perfectly legal. Let's walk through what's happening here. We're declaring two variables, and our condition is It's pretty much a standard condition. We just put on your statement in there. So if either one of these true, if either one of these is true, our loop will continue and at the end were implementing two different variables. The two we declared at the beginning. But we'll discuss why we're doing this as we go through it. So we want to also create a variable to keep track of the number of mutations we have so far. And we'll started out zero and in here, basically, when we want to go through with strings one by 11 character at a time and look at the number of mutations. So so how do we tell if there's a mutation? Well, let's must check if the characters are just equal. If the characters are exactly the same, we want to do nothing and we want with the loop continue. But if they're different we want to do something. So if they're not equal, we know we have a mutation so we can school ahead and increment that. And now we need to determine which type of mutation it is. Is it a deletion and insertion, or is it a substitution? So we've increased mutations and there's another check we actually want to dio. So we've implemented mutations, and if we already know, we have to, we can immediately return false if not itself. It's the first mutation. Then here's what we want to do. So here we're saying the length of the first item is greater than the length of the second item. So this could be an example for this one or this one. So if they're equal, we actually want to deck Ament the second variable. And let's explain why that IHS taking this as an example. So we're comparing a and A in our loop and they're identical. We're comparing B and C, and these are actually different characters. So we're gonna enter this loop mutations is going to become one. We're going to skip this because mutation is equal to one, and we're gonna go in here. So we're gonna decrease J. And that's the index right here. So we're at the next one in both of these, and we're gonna we're gonna decrease the index for the second string and bring it back down to here. So again, for the first string, where at B for the second string, where at a Let's go on to the next to the next iteration of the loop and this dream we move on to see. And in this string, we also want to see So essentially, we've gotten second string back on track by performing this operation right here we compare C two c even though they're at different indices and then we keep going. Since they're identical, then we increment both indices again. And de as the same is deep. So we're good to go. We know that we've only had one single mutation and now we can return true and we're almost done here. But what do we want to do if there's an insertion instead? Well, in that case, then string one is going to be shorter than a string to, and we're doing at this case, for example, for this one, we actually want a deck Ament, the other variable, and this will again put us on track. You can go ahead and go through this on your own and work out that logic. But it does work. This is the whole function. Let's go ahead and test it. We'll go ahead and use thes. So here we expect to see true. Well, this is trying one of each of these running again. True. And let's try this, uh, made a mistake there, and it's true. And to make sure it's working, let's also try something that doesn't work. Shouldn't work. So here we have two additions, so this should be false, and we see that it is false. Let's try to. Substitution is instead so a BCD becomes a x x d. And again we get false. And let's try to deletions false again. So this does work. Let's go ahead and go through the time and space complexities for this function. So in the for the were going from I equals zero to the length of the string. The strings I and J, we are only using one loop here and in this loop, none of these operations are linear thes air, all constant time operations, so they're not going to change the time of complexity of our loop. We just have to figure out what the time complexity of this one single loop is, and it's going to be linear. So generally the strings. We're going to be similar length quite similar. And so we can say N is just the length of either string. In that case here, the time complexity is going to just be, oh of N. You can argue that we go through twice as many because we are dealing with both variables, I and J. But that would just multiply this by two, and we get rid of the constant anyway, So that would leave us with a time complexity of o of n and what's the space complexity? Well, no matter how long these strings are, we only store three variables I J and Mutations. So that's actually going to be o of one hope that helped. And I hope that makes sense and I'll see in the next video
8. Detecting Anagrams: you all anagrams. The instructions here are to take in an array of strings and return. True if all of those strings are anagrams of one another, anagrams means they have the same characters in the string, but they might be in a different order. Here are some examples these three are all anagrams of each other. They all contain a, B, C and D, and they're just in a different order. In the next example, we have an X here, which means they're not all anagrams, so we'd want the function to return False and the next two are pretty similar to those. Go ahead and try it yourself and let's go ahead and get started with the solution here. So, as mentioned an anagram or rather, anagrams, our strings that have the same characters, but perhaps in a different order. So what's one way to figure out if two strings are anagrams? We could keep account of each character, and we could check those counts at the end once we've processed the strings. But there's a way that's a little bit simpler, and we're gonna go with that way. First, we can actually sort these characters. So for example, if we sort a B c D, it'll stay exactly the way it is. If we sort this next ring, it'll turn into a B C. D and do the same thing for this one, and it also becomes a BCD. The strings, after sorting them all, become the exact same string. So if we sort anagrams of one another, they should all become the exact same string, and we can use this to our advantage. Let's go ahead and start. So where is gonna sort every string in our ray using the map function? So we have a string and we want to first split it into an array. So now we have an array of characters. Then we use the sort function, and then we join those characters back into an array, and this will contain the strings, all sort of together. Let's make sure we got that right, and that's tested with this one. Oops, that looks right. So, no, we have to do. Let's go through these strings and a loop, and we need to make sure they're all equal, as we said before, and we have to want to start this at zero. We're Sorry one. This is our whole solution. And to make sure it works yet, we get true. Let's try all of these. So doing them one at a time here, we expect false here, we expect true. And here we expect false again and this works. And what about the time and space complexities? For time we're going to have to consider this in terms of two different variables. Normally, we just use n and we say over and or in squared or whatever. But here, we're going to say s is the length of the strings and A is going to be the number of strings in the race or just the length of the array. This is because the time and space complexities are extremely dependent on both of these variables. It just makes sense to use both of them. When we're talking about these time complexities, time and space complexities. So the time complexity. Let's go through this one right here. We have string, not split. So again, a map is a loop. So this is already going to be oh of a since we're moving over the array and then whatever we do in here is going to be multiplied by that because it's inside the loop. So sorting a single string is going to be s times Log of s a sort Operation is generally taken to be n times long of end and in here is going to be the length of our string. Joining them again is going to be It's going to be Oh, of S which is the length of the string again So we can actually add these together. So split I think I completely forgot the split part That's also going to be just s so s for splitting s times Log of s for sorting and s again for joining as plus s long else plus s And we can actually simplify that and to a times to s plus terms Log of this and this entire term can actually disappear because s times log of s is higher order than yes. Since these two are different variables and us, we have to keep both of them. This yields a times s times log of s for our time, complexity. And what about space? Well, we store an entire array of items and that array is going to be the same length as our initial Valerie. So that's going to be oh, of a length of the array. And each of those strings is actually going to be the same length as the original strings. So it's going to be a time. It's s because we're storing the same number strings, then the strings. We're going to be the same link. So that's our time in space complexities for the solution. In the next video, we'll go over another solution and try to improve both of these a little bit. See you there.
9. Rapid Anagram Processing: welcome back to all anagrams. In the last video, we wrote a solution that at a sort, each of the strings and then determine if the strings were all equal to each other. Here, we're gonna work on our solution a little bit and bring down those time and space complexities which looked a little unwieldy in the last video. So instead of sorting, we're going to try another strategy, and that strategy is going to be counting up the occurrences of each individual character. So, for example, taking the Serie we're going to want to create an object that tells us how many of each character are in this string. We're gonna want to do the same thing for the next string and make sure those two objects are the same or that they look exactly the same and do the same thing for this third string and on and on and on. And we just have to make sure that those objects keeping track of our characters look exactly the same for each and every string in the array were given. Let's go ahead and get started. So we're going to need a lupas usual. And what do we want to do in here? Well, we want to create an object with the character counts of the string. And how do we do that? Well, and we've done this a few times before when we need to dio start by creating an object and then we'll act. You're gonna need another loop. This loop is going to look like this. - So pretty straightforward. We've done this several times so far. This is just a loop that's going to fill this object up with the character counts of whatever string we pass in. If it's the first time we're processing the character, then it's not gonna be in our object yet. And when we search for it, we're gonna get undefined. Then we wanted to set its value to one. If it already has a number meaning it already exists in our object. We just want to increase that number by one. We can clean this up a little bit just to make it easier to read. And just to make sure we did this right, let's consul log object. So running it with just these three strings and that looks like it's working exactly the way we want good to know. So we have this object and what do we want to do with it? Well, we want to compare it with another object for another string. And how do we get that object? Well, weaken, just do that before the four loop. So here in our loop, we can actually start with item one, which means we'll start with this string. And before we actually start the loop, we can go ahead and create the object for this very first string. So essentially, we want to create an object for the first string. And that's actually going to follow just all of this logic except instead of so instead of the string this is going to be strings is zero. No, What we have here is we have essentially the same code written out twice. A good thing to do would be to extract this into another function so we can go ahead and do that. It will help us out and clean it for quote a little bit. - And that should work so we can go ahead and get rid of these and just use our new function. I can't get rid of all this and user function again. No, we're comparing. The object would generate here with the object generated appear which is going to be for the first string. We need to make sure that every property in those objects is equivalent. And we actually need to do that with another loop. - Almost there. Now, this should work. Let's go ahead. And we're on it just to make sure we get out of true. Let's try this one falls true and false. This looks like it works. So we've seen that our function works for these four. But let me show you an example where our function actually returns the wrong result. So if we had a knee here and we run it, I need a comment these out. We expect falls because this has an extra e meaning these three aren't anagrams, but we get back true. And this is because what we're doing here is we're first creating an object for the first character. Count the first string we get. Excuse me. So that object is gonna look like this. It has a through e and each have one. That's what we want now in here. As you can see, we're missing the so we have the e in the first string, but not on the 2nd 2 strings, and we can see that all here. Now, the problem is in this loop, all we're doing is returners checking for the characters that we see in these two objects. So we're checking to see if a in hairs equal toe one and it is B is equal to one. C is equal to one, and D is equal to one. We don't check to make sure that there aren't any extras. So this actually passes are check one it shouldn't. And there's a few things we can do to get around that. What we're going to do is probably one of the easiest and one of the least time time intensive. So we're just gonna go ahead and do that. And what we want to do is create another loop to go through the string. Sorry. Go through the array and just make sure that all the strings have the same length. Simple enough, we start off at one and go towards the end and just make sure all lengths article So again , we know expect this to return false, and we do get false back. So we fixed our code. This is it. This is our whole function. Let's go through the time and space complexities. So for time would start with the top live we have here. We have a lot of a We're looping through the entire array and making sure that strings are the same length. So that's just a loop through the array down here. Let's figure out the time complexity. Forget car count. We're going through a loop and processing every character in the string. So there's going to be a standard loop that takes a link that takes time proportionate to the length of the string. So there's going to be Oh, of s, that means this whole thing is Oh, of s, this right here is going to be over a since it's a loop over the entire array and then this and here is going to be over s so this turns into of a times s This one here is also of s So it's o of eight times two s, but the constant gets dropped. So we just get a of s. And that's our final time. Complexity for space. No, matter how large the strings are A is All we do is create just a few variables we create. I we create first car council. This is an object. Let me get rid of these. It's so I don't confuse ourselves. So here I This whole loop is just going to declare one very I So we can ignore that This right here is going to be Oh, of s because we have an object filled with the character counts of a string and that object size is going to be proportionate to the length of that string. So there's going to be a Nove s right here in here. We can create a variable I, which has been significant. And here we create another variable, Oh, of which is also going to be over s. It's an object that is proportionate in size to the length of this string. So and in this four loop, we don't do anything, uh, with space. We don't really create any objects here or any variables at all. So we have a no of s and another o of s. And these are going to be added together because this stays for the length of the function for the length of the remaining function. And this object here gets generated when we start the loop and then deleted once the loop ends. So this loop Onley spawns one of thes objects at a time, so at most at one time, were using O of s plus s space, which gives us off to s, which simplifies down to O of s. And that is the final space complexity for this function. Seeing the next lesson.
10. Rotating a Square Matrix: problem. Rotate, matrix, matrix and Java script can be represented as an array of a raise. And here's an example. We have one single outer array which is denoted by this bracket in this bracket here and in here. We have three arrays, each with three elements in them, and this constitutes a three by three matrix. Our goal here is to write a function that will take this input. So the input is going to be this array of arrays and outputs a new matrix. So we want the function to return an array of a raise and that new matrix that's returned should be the same as this one rotated 90 degrees. This should work for both square and rectangular matrices. So basically, major sees of any dimensions for the example given this matrix as input and we can ignore these thes air indices just toe just to see where these numbers are located. Given this matrix as input with this array of three arrays, we want our function to output This matrix. As you can see, everything is just rotated 90 degrees clockwise. The one gets moved to the right, three goes down, the nine goes left and the seven goes up and everything else moves with the four. Sorry, the two moves to the right and down the six moves down and left and on and on. So essentially we need to rotate this matrix 90 degrees clockwise. Go ahead and try the salad on your own. It's pretty fun, and it's not terribly difficult, but come back when you're ready. When you've tried the problem, let's go ahead and start to solve it. So the problem states that the original Matrix should remain unchanged. And what this means is that we want to create a new matrix to return. We don't want to just move things around in the original, but we want to make a new one. So let's create that. So we're just going to start out with an array and how do we fill this matrix? Well, let's just start with a square matrix for now. So let's examine this three by three that we already have. So if we have a three by three is input. We know our outputs also gonna be a three by three. If we have a four by four. Are outputs gonna be a four by four. So the number of a raise in here and our new matrix is going to be the same as the number of a raise in the old Matrix. And we can figure that out using the length property, this outer array has a length of three because it has three items inside it. So we can use that to just create the same number of rows for this new matrix. And that's our new Matrix will have the correct number of a race in it. And let's make sure we're doing this right as we go along and we'll run an example. Go and steal this. Okay, there. So we have an array of three race as intended. We now also know at the end we we need to return this so we can just write that statement. And now, Now what do we do in the middle? We just have to fill The Matrix with the correct numbers, and we're gonna do that by looping through The Matrix were given. So we're looping through here and we're actually going to have to loop inside each inner hurry. So right now we're looping through this outer array and the current role where on is going to be this one? And then the loops gonna move on to this one. And in this one, we need to also look through each of these to get to these numbers individually. Here we're using matt zero dot length. Actually, this can just be changed to math that link. That's the same thing, because right now we're just focused on square matrices, and the number of items in here is going to be the same as the total number of a raise. So this is going to work for us just fine. And now, for the hard part, we have to actually figure out how to move thes items to the correct place.
11. Rotating a Square Matrix Solution: Welcome back. Let's keep working on this problem. So far, we have the foundation laid out, and now we just need an algorithm to actually move these pieces to the correct spot. And let's go ahead and work on that and for examples. For an example, let's start with a simple two by two matrix, so I'm just gonna go ahead and use one, too. This needs another bracket and 34 and this needs to turn into 31 four to, and that is a 90 degree rotation. So let's go ahead and map out the actual position changes that happen. And what do you mean by that? Is this so one here is at position 00 It's at row at Index zero in that row. It's at column zero so we can say 00 moves to still in rose zero. So that stays the same, and it's known Column one. So that's going to move to 01 And let's do this for the other three as well. So we get an item at 01 moves to 11 and we get an item at 10 Moving to where's through? Move 200 and we get 11 moving to 10 And that looks right. So from here, we can actually go ahead and create an algorithm. If we do this for three by three or four by four, or any square matrix, we're going to get the same results. And those results are going to be governed by a simple mathematical rule, which is going to be this. Forgive me for the type of lives and just to make sure that we're doing this right, I'm going to long this out. So 741 852 963 That is exactly what we want. And let's show you how this is actually working. Let's plug in some numbers. So plugging in 00 here onto this into the right side, we get New matrix, so Jay is positioned. Zero. So that's days. Add zero. So that's correct. The very first item is going to be zero, and the second item is going to be matt dot length. So the length of this matrix is, uh, length two. There's three items, but its length to so two minus one is one minus I, which is zero since we're starting at 00 So 00 plugged in here leads 20 comma one on the left hand side. So we've actually turned 00 and 201 We've moved the item from 00 to 01 We can do this for the rest of them. We can plug in 11 here, and what we get is one in the left hand position and Matt at length to minus one minus one . We get zero here, so we've turned 11 in 210 Go ahead and plug in these two. Or try whatever else you want. It'll work every time we've solved this problem for square matrices and in the next lesson will go ahead and try to apply this to all maitresse. Ease. See there.
12. Rotate Matrix: Two Bonus Problems: welcome back in the last lesson. We did indeed finish this problem. But I want to go ahead and give you guys a little bonus. So the first bonus problem is going to be right. A function that all rotator matrix 180 degrees. And the next one will be right. One that rotates it 270 degrees. You could also think of this one as negative 90. We have this one already. I just collapsed it. Teoh, make room for the others. This is the exact same function we had before and nothing's different. I'm just collapsing it. And these are expected outcomes for this matrix. So rotated 90. We want this 1 80 Want those 2 70? We want this. All we have to do is write thes two functions. There are a few different ways to do them. Go ahead and try if you like. If you want to go ahead and just watch the video, you can do that too. Since this is just a bonus, I'll let it slide. So here's how I'm gonna solve this problem. And that's a done. And that's also done and is making sure these line up during 14 to 4321 2413 And we are good. Do you think this is cheating? I kind of do, too. But the point is, it really doesn't matter. These functions work, and they work perfectly well. And there's actually reasons you would prefer these over another big function like this. Your most valuable resource as a developer is your own time. It's not the amount of time the machine takes to run your code. These results are blazing fast. I had run and before I can think the results are there, and that's gonna happen for almost every function you write in your entire career. Computers air fast People are slow, so you want to spend your time writing as little code as possible. We've written one function that works perfectly, and we know it works. We've tested it a little bit. Why not reuse it? If we can, we just reuse it. We call it twice, and it rotates our function 1 80 degrees. We call it one more time, and it will do it 270 degrees rather than writing the same essentially the same code with a few differences again and potentially introducing bugs. When we try to do that, we can use the one function we know, works and save a ton of time doing this the easy way instead of the hard way, the time complexities of thes functions are going to be the same as the original. So remember this waas for time? Oh, of n and this one is going to be We're just doing it twice. So two times in and we drop constant, so it's going to be in. Anyways, this one was going to be three times in, which is again going to turn into oh, then space is gonna be the same thing. So space complexity for this one was over then, because where creating an entirely new matrix with the same items here, it's going to be also of in again. We were multiplied by two. Since the function gets called twice, we have two of these and memory at once, and the space complexity is also going to end up being of any same thing for this one. That's it. I hope that was fun. And I'll see you in the next video where we actually learn how to rotate a matrix in place . And what that means is we can't create any raise or any additional data structures in our function. It's a much harder problem, and we're gonna have to rewrite everything, so I'll see you there.
13. In Place Matrix Rotation - Strategy: welcome to the next problem. Rotate matrix in place. It's the same exact thing is the last problem. Except in this case, we know we're always going to get a square matrix, meaning a three by 3555 10 by 10 whatever. And our goal is to rotate it 90 degrees clockwise. But this time we need to do it in place. And the key to what in place means is you can't create any extra matrices or a raise in your function or any other data structure. Really. All you can store is variables. Go ahead and try this on your own if you like. I'm going to warn you. This one's very difficult. And even once you figure out how to do it, the code is very difficult to write. So I'm gonna solve this in two problems. First will go through and discuss the strategy we're going to employ, and then we'll show you some code. So I have a little sketch pad here. Oops. And let's take this matrix as input and just discuss the strategy we're going to use. So here we have a five by five matrix and we're just gonna use this as an example. Now I'm going to go ahead and take out the essentially the perimeter of the Matrix. So we're going to pretend that the inside doesn't even exist. All we care about is Thea outer rows and columns. And what we want to dio is this. We want to take the upper left hand number and move it over here. So we want to move this out here. But before we do that, we have to figure out what to do with this number. We can't just override it because this number needs to move down here and this one needs to go over here. And finally, this one needs to go over here to complete our little circle. So by the time we've done this one's moved here, Fives moved here, 20 fives here and 20 ones up here. We've done a full 90 degree rotation of the corners, so these corners have been rotated fully. Now what we're gonna want to do is keep going. So start here and we're gonna need to move this guy over here and the 10 is going to move to the spot of 24. 24 is going to go to 16 and the 16 is going to replace where the two originally left from. So now we've got ahead, and we've rotated 2/5 of this entire outer perimeter, and we need actually half of it. Sorry, because we only care when he needs to do this four times. So when you to do it for the corners and then this item in this item and then the four over here, we've already done the five that was already taken care of. So we just needed to this four times. This is what we're gonna need to code once we're able to replicate this and I won't draw the arrows again because that will just make this unnecessarily confusing. But once we figured once we've done this, we can then move on to the next row. We're not next row. Sorry. Next perimeter. So I'm gonna go ahead and grab this out of here, and I will try to move it a little bit lower and switch back to the pencil. So once we're done with the outer perimeter, meaning it's entirely rotated, we can move on to the next inner perimeter, and we just want to do the same exact thing. Move this guy right here. Move this guy right here and on and on. And once we can do that, we can move on to the next one. In this case, since we only had a 555 the very last perimeter will be the number 13 by itself. And we can leave that, as is so we really need only need to do this twice. In this case, if it's seven by seven will need to do it one more time if it's a nine by nine and then another time. But this is the strategy we need to code. Go ahead and try it on your own. And in the next lesson, we'll show you the solution and show how it works.
14. In Place Matrix Rotation - Solution: welcome back to rotate matrix in place. Rather than solve this problem. Live as we've been doing for the past several problems, I figured it would be better to just show the solution and talk about it. This problem is perhaps the most technically challenging problem in this whole course. So rather than fumble over my coat, my code as I fumble trying to explain it to you, I figured it would be easier to just write it out and explain it afterwards just to make sure it works. Let's go ahead and run it. So for this matrix right here, we expect this as output. And if I had run one more time, we get just the same thing and it's exactly what we expect, which is good. Let's go ahead and show you the code and talk about what each line is doing. So lying 21 This is variable. Total layers is going to hold a number that tells us how many layers we need to go through . And what I mean by a layer is each one of these. So this right here this perimeter is one layer that we want to go through. We want to rotate every item in this perimeter and then move on to the next layer, which will be this inner circle right here. So if we have a matrix that's a five by five. We only need to go through two layers. And this formula right here will tell us that inner for loop, we go from zero to the number of layers, as we just mentioned. And that makes sense. And this line right here is determining the stop condition for our inner for loop. And the way that works is we're going to start at layer plus one. So what that means is we're starting. So when do we start with this Matrix layers essentially is initially going to equal zero. So we're saying we want to start at index one, Which means at the 02 right here the stop condition, which is going to be matt dot length minus layer, means we want to stop at five minus zero. So we want to stop right here. So when we went through this exercise, we started at 01 and we ended up Oh, for our loop is instead starting at 02 and ending at 05 which will work just the same. So we moved the two to the tens, place that 10 to 24 24 to 16 and 16 to 2, and then we move on to the three and rotated and then the fourth and then last of all we do the corners. This code in here is doing all of the heavy lifting. So when we're moving the two over to the 10 we're going to need to store the 10 in a variable before we can replace it with two. If we just override it, then we lose 10. So we need to store this and then update its value. We then need to store the 24 right here, and we need to replace it with the 10. So we're actually going to need two different variables. Tempel one and attempt to temp one is going to be storing the the 10 initially and temper to is gonna be storing 24 will rotate their use So the 10 is going to move here, and we're going to knock this into a variable. Then 24 is going to move to 16 which we're going to store in a variable and then 16 is going to move to where it's happy. You're likely need to go through a matrix rotation by hand to observe how this works. Keep track of each of the variables and keep track of what's happening literally. Try drawing a matrix on a piece of paper and go through this code. Once each of these is swapped and the entire layer is rotated, this inner loop is going to be finished, and this outer loop is going to increment. So we're going to move to this layer, and we're going to do the same exact thing. So our loop is going to start at the eight and end at the nine that's going to rotate the A to move it to the 14 move the 14 onwards and onwards and onwards, and then it's gonna do the corners after that. So then it's gonna move the nine to the 19 and on and on and on at the end. We just returned the same exact matrix we were given. Whatever the time and space complexities well, we only process each item once we rotate a layer, and then we move on to the next layer, the time complexity is going to be off space. Complexity. Well, we're not creating a single data structure anywhere here. All we're doing is using variables. It doesn't matter how big the Matrix is. We use the same number of variables, so that's going to move to O of one. This one is rough. If asked in an interview, you'll most likely be asked to just give the general strategy you'd use and maybe talk about the efficiency a little bit. Getting it correct could take a good programmer hours, which would be much too long for an interview. This problem is great in making us think about how to spatially transform data. The ability to understand the solution shows powerful reasoning skills and excellent spatial reasoning as well. If this is too complex, try coming back to it another time. Try walking through the function using a simple matrix such as a two by two or three by three. Keep track of each of the variables and what's happening to the Matrix. Go ahead and try it yourself for any square matrix you like. I'll see you in the next video
Arnav Aggarwal, Full-Stack Engineer & Instructor
