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. Unique Characters: welcome to her first problem is unique. The goal here is to write a function that will take in a string and determine whether each character in that string appears only once. Essentially, we're trying to see if each character in the string is unique in that strength. We wanted case sensitive, meaning both lower case and capital versions of a letter in the same string are considered unique. Here's some examples. We get a normal string A, B, C, D E f, and everything's unique, so we want the function to return. True. This next example just shows that we want our function to be able to accept a string with any type of character, not just letters. Again. They're all unique. So we get true. This third example again shows that a lower case A in a capital A in the same string would still we would still want our function to return. True for that input, the 4th 1 shows a duplicate lower case eight and her function would return false. Let's just go ahead and start writing this function right away. So to make sure every character in our string is unique, we're going to need to process every character in the string, so we know we're going to need to loop. Let's go ahead and start there. What do we want to do in this loop? Well, one strategy we can employ is the following. Our loop here is going to go through a string left to right. So taking this as example, we're going to start at a. What we can do is we can have another loop going from right to left looking for that same character. So while our outer loop is on a, we can have an inner loop going from right to left. Also looking for a if it finds it and it's not in the same position that the outer loop is at, we know that we have a duplicate and we can immediately return false. If there's no duplicate, this will run all the way until it gets to the A over here, and we know that it's unique in the street. We can repeat this going left to right as our second loop goes right toe left. For each individual case, this might seem complicated, but there's a little method that makes us very simple for us. Let's write it out and discuss it right after last index off. This will do exactly what I was just describing. It will go through the string right toe left, looking for the character we provide in this case, whatever character that I is currently on. So again, we give it a in this case for the very first round, and it's going to go right through left looking for a So what we're doing is making sure that the last index of A is the same as the current index that were that were on. This will show that the that the character is not duplicated in the string. If, however, the the last index off A is not the same as the first index of a, then we can immediately return false Um, that's really all the logic we need at the end of the function, we can return true, it only get here after it's processed every character here and made sure that there's no duplicates, dysfunctional work. Let's go ahead and runner code here, and we expect to see true, true, true, false and that's exactly what we see appear so our function works correctly. Let's go through the time complexity of this function so we can see that we have a for loop and that immediately brings our time complexity to O of n because every single character is being processed right here. We actually have another loop in the form of last index of Well, it's not a loop that we wrote. It is a loop that is going through the string from right to left. So this is actually another o of end. Since this is nested inside the outer loop, we need to multiply these time complexities to give a final time complexity of O of n times n oh of n squared. What's the space complexity? Well, let's think about it. No matter how long the string is, whether it's three characters or 30 or 300 we're only ever using one variable in our entire function. And that is, I were only storing one character at a time. No matter how larger input is, our function takes up the same tiny amount of space. So we say that it uses constant space, or O of one. That's it for this version. The solution. Can we improve the time complexity a little bit. Yes, we can. Let's go ahead and try that. There's something we can do it before we go through our string to make it a little simpler , we can sort our string. So let's go ahead and try that. So what I've done so far here is I'm taking the string and splitting it into an array. That's what this method dot split does with an empty string right here. So at this point, cars would just be equal to an array of individual characters in the same line we consort it. The characters will now all be sorted from left to right. So if we were given something like D B A C, it would look like it would have an array. It would now be an array of A, B, C and D. Simple is that what can we do now that our characters are sorted? Well, there's a different piece of logic we can apply to make this a lot easier. We're going to need the standard for loop again. Actually, I was going to start at one for this one, and we'll explain why in a second so now. But the I don't know what the characters are sorted individually. If there are duplicates, they're going to be placed right next to each other again. Assuming we got D B A. C A. This will now turn into a B C D. The two duplicates appear right next to each other. So what we want to do is for this string, or rather, this array of characters. We want to start at the second character, and what we want to do is compare it to the character before it. If they're the same, it's a duplicate, and we can immediately return false. Let's code that out. That's it. This function works perfectly as well. Let's run it just to make sure again, we're expecting True, true, true, false. And that's exactly what we get. Let's go and clean this up a little bit. And again, let's talk about time and space complexities. So in this case, we're starting with a store to right here. Now, different sorting algorithms have different time complexities, but in general, if we're talking about a sword, we can assume the time complexity of O of end times. Log of n This here is a standard loop. It's just going to be Oh, of N because these things happens sequentially and we don't have a loop inside a loop. We can simply add these. So we're going to start with O of M Times. A log of end plus o of N, which turns into oh of N plus n times along of End and N is a lower order term than this right here. Let's simplify this further to show exactly what that means when we're talking about time, complexities weaken. Simply eliminate the lower order terms so we can get rid of this one plus and our final time complexity ends up being exactly this. Oh, of end times long of them and that their time complexity for this solution. What about space? Previously it was over one, but now we're taking each character and we're storing it in a hurry. That's what happens here. So we're storing each character, meaning we take up the same amount of space as the size of the input. So it's going to be, oh of, and we'll talk about two more solutions in the next video. See you there
3. Rapid String Processing: welcome back to his unique. We've now gone through two solutions, and we've managed to improve the time complexity from O of and squared Thio of End Times. Log of End. We accomplish this by sorting the string we get as an input. We can actually make our time complexity even better. And that will require a different strategy. Let's go ahead and erase all this and start over. So last time we had sorted the string. You want to do something different This time, we're going to create an object to store characters As we come across them again. We're gonna need a loop going through our string and it doesn't like something. 04 loop. So what we want to do is check if our object has already contains a copy of the character work currently processing. That's it. This is actually the whole problem is just that. Run again and make sure it's working fine. And it is not working fine. What's going on? Uh, returned False down here. This needs to be true. There we go. My apologies. So let's walk through what's happening here one more time as we go through each character, for example, Let's take this string right here. ABC A e f. We're going to process each item individually. So the very first time we go through this loop, this car is going to be a We're going to check if our object already contains it. And if it does, we want to return falls. Our object is empty at the beginning. So this check passes and we move on to here. We're going to store a into our object. We're just going to set its value equal to true. So our object will contain every character we've already processed so far. As we go through the string, we're going to add in a and then B and then see when we get to the next a were again going to check if cars has the character A And if that eagles true, since it does, because we've already seen it and we've already inserted it into our object. We know that it's a duplicate and we can immediately return false. If we get through this entire loop, we know that there are no duplicates and the string and we can return true. That's it. Let's talk about the time complexity in this version of this function. We only have one loop. We're going through each character and as we go through each character, the things we do in here are constant time. There's no more loops or anything of that nature. So we have a single loop giving us a Tom complexity of o of N. What about space? Well, every character become across is being stored in our object. So space is also going to be a love N because it's proportional to the size of the input. There's a way we can change this up a little bit. Instead of an object, we're going to use an E S 2015 construct called a set, now a set a similar to an object. Except it's more appropriate for this exact task, a sudden as a data structure meant to hold unique items. Let's actually go ahead and look at the Indian Page four set as we can see, a set, is an object that lets you store unique values of any type, uh, in a set. So a value in a setting may only occur once, and it is unique in the sets collection. So this is a data structure specifically made. Essentially, for this problem, we just need to change a couple of things. For example, Instead of this, we need to use a built in method and same thing here instead of setting. Instead of setting our item to true, we're going to simply add it into the set. We don't need that. And we don't need that. And again to make sure this works. It does indeed give us what we want. True, true, true, false. Again, This is very similar to an off to the method we had before with an object. The only difference is we swapped out or data structure. And there's actually a very good reason we did this. It will allow us to write our solution in a new way and even simpler way. And we'll discuss that in the next video. See, there
4. Unique Characters: Ultimate Simplicity: welcome back to his unique. We've now cover three different ways to solve this problem. For the last method, we showed how to do it with both an object and a set. Now you might be wondering why I showed you this set. It does the same thing as an object, and it doesn't really offer anything new. It's just another thing for us to learn and get used to. Well, I want to show you the true power behind a set, and I want to show you a way in which it can make our solution much, much simpler. So before we do anything, let's dive into some of the properties of a set. Let's just create a new one here and let's throw in a few items so we'll give it an array with the numbers one through five, and let's off this out. So as you can see, when we give us set an array, it'll take each individual item in the array. An added into the set. Now what was un intuitive, at least for me, was what happens when we give it a string instead? Hopes so let's go ahead and get rid of this and instead give it the string A B C D e. As you can see, what happened is each individual character in the string got inserted into the set. One by one, the string essentially got split apart. For us, this is very important. There's one more thing I want to point out and that is the size property. So a string has a length property, which tells you the number of characters in the string. A set has a size property which just tells you the number of items in the set. So, as expected, it's five because we have five different items in the set. I want to show you one more thing, which is what happens if we add duplicates. Let me go ahead and add ABC again and we run it and we see that the output here is exactly the same because set again can only contain unique items. And the characters A, B and C are already in there. So it completely ignores thes three. And the set contains five items as we can see right here. Let's go ahead and go back to our problem. I'm gonna erase all of this and I'm gonna write a line of code and we'll talk about it right afterwards. That's actually the entire solution. And let me run this just to show that it works. And it does. Go ahead and test it out on your own if you wish. It'll work every time. Let's discuss why this is as shown before over here. If we are duplicates into the set, they'll be completely ignored. That's what's happening here. We insert a string into the set, and each individual character is being inserted into the set were then checking to see if the size of the set is the same as the length of the original string. If there were no duplicates than the size of the set, should be exactly the same as the length of the string. However, if there were duplicates on the settle, be slightly smaller. By returning this comparison directly, we've solved the whole problem if their unique this equality of the true and the functional return true. If there are duplicate characters, this equality won't hold and the function will return false again. Let's go through the time and space complexity for this function. We're taking a string and we're adding it into the set character by character. That's a linear operation. So it's O of end space again were adding each individual character into the set, so it's gonna be proportional to the size of the string. So once again, oh, of n let's quickly wrap up by talking about everything we've covered so far. The first solution we came up with was the brute force solution that had an oath and squared time complexity its simple, straightforward. And it's the first solution that most people come up with. If you can identify the time complexity and then work to make it better, you'll face this question in an interview. The second solution involved sorting the string. First, it was better in terms of time, complexity, but we had to increase the space complexity for that solution. The third and fourth solutions are ideal. We have the lowest time complexity, and we reduce it down to O of end, which is a very significant improvement. The 4th 1 here is clever, but the 3rd 1 would have been more than sufficient. In an interview, they both achieved the best time complexity possible. The main idea is to take away from this is that applying various techniques to a problem, Consignia efficiently improve time or space complexity. Sorting our data brought it down, brought down our time complexity and then, using an appropriate data structure, either an object or set improved it again. We'll see this popping up again and again in the future problems. Try using an object array set. Stack our cue or any other data structure and see if that opens up any new avenues for your solution. I'll see you in the next problem in the next video.
5. Flattening Nested Arrays: welcome to our second problem flatten array. In this problem are input is going to be an array of nested arrays, sometimes deeply nested arrays. And our goal is to write a function that will take each individual item in the array and extracted out into a new flat array. Here's an example. We receive an array that has several or raise inside it, plus other items. The goal is to get those items out of their deeply nested arrays into a single flat array while preserving the order. The inputs can be numbers, or they can be strings, or they could be objects that can really be anything. Our goal is to take them whatever they are and put him into one flat new array while preserving order. This problem has some practical uses into a developers career. I've had to deal of nested data sources plenty of times, and solving this problem will give you some insight on how to solve similar problems that arise in the future. Unlike the last problem where I showed solutions and then discussed them, I think it'll be more instructive in this case to walk through the solution. So let's go ahead and get started. I encourage you to pause the video and try it yourself first. Let's go ahead. So we need to create a new array. First, let's go ahead and do that. Okay? We're going to need to go through every item in our memory and process them one by one. So we're going to need a loop. Okay? I'm just gonna store the current item into a new variable. And what do we want to do in here? Well, we're going to want to do something. If this item right here is an array and we're going to want to do something else if it's not in hurry, If it's not an array, then we can immediately push it into our new array. But if it is, we need to go through each individual, item the school head and start coating that out. So first, what we want to do is check if this item is an array. So if this item is not an array, we know it's not nested any further, and we can go ahead and push it directly into our new array. However, if it is an array, what we want to do is take each individual item inside battery and push those one by one into new array. So we're actually going to need another loop in here, and at the end, we want to return our new array. Okay, so this function right here will work if we have an array nested one level deep, for example, say this is our input. Our functional correctly work for this array, and it will turn it into an array that is not nested. That looks just like that. Just to make sure it works. Let's go ahead and test it out. And it does work. Let's go through why this works. So we're inner for loop, and this item, the very first time, is going to be the number one. It's not an array so ruin to directly pushing into new array, which will now have just one inside it. The next time this item is going to be, too, and we're going to do the same thing and again the same thing for three. Eventually we get to this array, which has foreign five inside it, and we're going to go into this part of the if statement we're going to go through each item here and push each item, which is foreign five individually in. So it will just go ahead and add them onto new arrange again with six. We're going to go in here and push it in directly. And thats why this function works the way it does now. What happens if we have more necessaries? For example, If we have something like, Excuse me, something like that, it's not going to work because we're only going one level deep. Instead of going into this and pushing seven, it's going to push this entire array into our new array. So how do we fix this? Well, the key is actually in this right here, so we don't know how many levels deep we're going to need to go. For example, the seven could be another array deep. It could even go further, and it could just keep going. That's the problem we're trying to solve. So we don't really know how many times, and we're going to need to go because we don't know how deeply nested these items can be. Were actor going to need to turn this into a recursive function, and here's how we do that That's it. This will work. Let's go ahead and test it out just to make sure. And it works exactly as we expect. What did we do here? Well, we're saying that if we come across a nested array, we're just going to call the entire flattened function again on that necessary. Let's think about that. Let's see. We get to this item, which is an array nested. It looks like three levels deep. When that happens, we'll just pass it through. Flatten once again, so flattened the next time around low receive an array, nested two levels deep. Again, we're going to pass it in. It's going to receive this one, and again it's going to go through and receive this one. Eventually, it'll get to just the seven, and it will take that and it'll push it into new array. This will work no matter how deeply nested are. Array is
6. Flattening Arrays Discussion: Welcome back to flatten. Rickerson is a difficult concept, so I encourage you to take a few different inputs and walk through the function several times on your own. Make sure that you've convinced yourself that the solution works the way you think it works . Let's talk about the time complexity of this function. We have a four loop here, and we have a recursive call and even another four loop down here. On the surface, it looks like the time complexity is gonna be pretty insane on this one, but it's actually rather simple. Let's ignore the function for now, and just think about what it's doing to an input. Again. Let's take this one. As we go through the function, each item is pushed one by one into our new array. So our loop will go here and it'll process one and put it another way, little process to and put in our new array, and it will do the same thing with three. Once he gets to this array, it'll dive inside it and it'll process four and then five and then six. And then when it gets over here, it'll simply dive deep down, process the seven and then go all the way back out. As you can see, each item is processed only once. We have all these loops and we even have a recursive call. But in the end, each item here is processed. Once That gives us a linear time, complexity or oh, of end. And what about space? Well, each individual item is stored in her new array, so it's proportional to the size of the input again, Linear. That's really it to this problem. What you can take away from it is that Rikers in is a powerful tool. Any time you can see that you're going to be repeating something in this case diving into an array and you don't know how many times you might need to do it, you're probably going to need rickerson. Thank you. And I'll see you in the next video.
7. Removing Duplicate Characters: welcome to problem number three. Remove dupes. The goal here is to write a function that will take in a string. The function should return a new string with same characters as the original string, but with duplicate characters removed. So if our function is given a string with unique characters, we want to return that exact string. If there are any duplicates, we want to strip them out while maintaining the order of the characters. That's what these two examples air doing here. Let's go ahead and get started writing this function again. I recommend you pause it and sure at yourself and then come back to this video. We need to start this function by creating an array to store the unique characters in our string. Let's go ahead and do that. We're going to need a loop to process each individual characters. So let's right that inside this loop we first want to check to see if the current character were processing already exists in our array. If it's already in our array, it means we've seen it before and we don't want to reinsert it, so we just want to continue. If, however, it's the first time we've seen it, we want to push it into our array. Our unique cars array now only contains unique characters. What we want to do is turn this into a string and return that string, and that's the solution. Let's run it and make sure it works. And it does. Indeed, we see a B. C D appearing three times exactly what we want. Let's go through the time and space complexities for time we haven't outer for loop here. That immediately brings us to O of N Lord linear because we're processing every character inside this for loop we use includes this itself is a loop because it's going through this unique cars array and searching for this car. And to do so, it has to individually go through everything in the array. So it has to loop through the array from left to right, and that will stop when another finds the item or gets to the end. But it is indeed a loop, and because we have a loop in a loop, we're going to have oh of end times end. Since you're multiplying their time complexities, which leads us toe of n Square and that's our time complexity. What about space? Well, we have to take the string and insert every unique character into our array. So we have to essentially store the entire string again, almost the whole string, at least. So that's going to be Oh, of N because the amount of data we use is going to be proportional to the size of the input . There's a way we can make this time complexity a little bit better after a whole lot better . Let's go through that. So I'm adding an object to our array right here. Whenever we push a character into our array, we also want to add it to our object. Instead of checking the array to see if it contains our character, we now want to check the object. So we're gonna replace in this. This is no longer an O of an operation. This is constant time checking. If an object contains an item is a constant time operation. It happens pretty much instantaneously, as opposed to an array which has to be searched through from beginning to end. Since we no longer have a loop inside a loop, we only have one single loop bringing our time complexity toe a total off. Oh, of and there's a way we can make this a little simpler. It won't do much for a time or space complexities, but it will make the problem a lot more elegant and a lot easier to understand. And we'll go through that in the next video. See you there.
8. Remove Dupes: Ultimate Simplicity: welcome back to remove dupes. What we've done so far is solved this problem and then reduce the time complexity. We started out at over and squared, and by adding in an object, we managed to reduce it to O of end. There's another way to solve this problem, which doesn't change your time or space complexities. That makes the problem whole lot easier to think about. I'm just going to write out the solution and then we can discuss it afterwards. Let's make sure it works and it does. We get what we expect. This is the solution, and let's explain what's happening. We're using a set once again. So when we insert a string into a set, each individual character gets inserted into a set only unique values air stored. So any duplicates are going to be ignored and discarded after the set is created. We use this method called a ray dot from now what the raid out from does is it takes in an epidural, an adorable, and JavaScript is a data structure that maintains our keeps track of the order in which data was inserted and a set does exactly that. A set will keep track of the characters in the order they were inserted, which is exactly what we need, because it does that we can say that if set is an honorable and it will work with this method arrayed out from which will literally turned it into an array. So this statement right here is equal to an array containing the unique characters and the strength with their order preserved. All we're doing after that is using join to turn them into a string. The time complexity here is exactly the same. We take each character and inserted into the set one by one. So that's the loop. Giving us oh, of end. Joining it into an array is our sorry. Transforming it into an array is also old then and then, joining it as oh, of n once again. So we have three n and when we drop the constant, we stay at O of n for space complexity. We put every character into a set and then into an array. So we have oh of two n, which again becomes O of n. Hopefully the shows you just how powerful a set is and how much mastering data structures can help you with these problems. The more you know, the more you'll be able to apply these things and future problems. We turned what was about a 15 line function. If the two lines, it's much easier to read, understand and right, I'll see you in the next video.
9. Highest Frequency: welcome to the next problem. Highest frequency. The goal here is to write a function that will take in an array of strings and return. The string that occurs most commonly implicit in this problem is that theory you receive might have some duplicate strings, some in there several times, and we want the one that appears most frequently. If there are multiple strings with the same high frequency, we want to return the one that shows up first. Here are a few examples in the 1st 1 C is the only string that appears more than once, so that's what we want returned in the next one. ABC appears three times and D E F twice, So we want to see ABC coming out in the next one. They're both president only once. So sorry. And since ABC is first, we want that one coming back out and in the last one GH eyes and they're more times than any of the others. So that's what we want coming back. Let's go ahead and get started on the solution, so we're going to need to process every string that is in our array in order to keep track of the frequencies. So we're gonna need to start with a loop as usual as we get to each string or somehow gonna need to keep track of how many times we've seen it. Let's go ahead and use an object to keep track of these strings and in the loop. As we process each string, we can go ahead and update our object. So let's think of the first string. Let's go ahead and focus on this example for now, at I equals zero, the for first item is going to be ABC. Let's go ahead and create a variable for that. So this string is going to be A B, C and R Object is empty. We're going to want to add it into the frequencies. Object. Okay, so far, so good. Let's go ahead and see what happens if we move on to the next string again. ABC we're gonna be in here, and this string is gonna be ABC once again. But now this line of code isn't doing what we want. It's resetting the value to one which does nothing for us. We're gonna need some way to check if it's the first time our object has seen this string. If it is, we need to give it the value of one. Otherwise we somehow need to take the value and increase it by one. So let's start by checking to see if it's the first time we've seen this string. And if it is, then it won't be present in the object yet. So if it doesn't exist in the object yet, then checking for it should give us undefined. And if it's undefined, we need to give it a value of one. Who is the first time we've seen the string? If, however, it already exists, meaning it already has cemented your value 123 or whatever we need to increase that by one . This looks like it makes sense to me. Let's go ahead and long out our frequencies array. Sorry object just to make sure we're doing this correctly. And I'm gonna go ahead and get rid of these three for now and just work with this example so we see what we expect. A. B C's in here twice D E f. Three times and G h I four times on. Our object reflects that correctly. What do we need to do now? Well, we somehow need to find out which of these values is the highest. We need to know that four is the highest value here and that the string corresponding to that is G H I. We could do some processing down here. We could take each individual value in the object and then find the highest number keeping track. But we already have a for loop. We can only do that by, uh by updating a variable throughout the loop. Let's go ahead and create a variable to store the highest free conceit we've come across so far. And we'll initialize it to zero. And it's also creative variable for the most frequent string, and we'll initialize it to the first item in our strings are a in our loop. Let's go ahead and update thes every time we go through our loop. So they're only going to need updating If we have a new max frequency. Let's check if we dio this check right here checks if our new frequency meaning the value we just updated is higher than the previous Max frequency we had. If it is, we want to update that frequency number We also want to update the most frequent string because that means it's changed once as we go through this loop, these two variables repeatedly update as they need Teoh. In the end, most frequent strings variable here will contain the most frequent street. So we can just go ahead and return that. Let's add these back in and make sure everything is working as we expect, So if it is, we expect to see see ABC, ABC and G H I. And that's what we get. It seems to be working correctly. Let's go ahead and talk about the time complexity of this solution. We have a loop here immediately. Bring us 20 of end inside the loop. All we do is perform a few checks and update a couple of variables if necessary. Those aren't loops in themselves, so they're not going to change our time complexity. So our final time complexity is going to be o of any And what about space? Well, we're storing every string we find into our frequencies object. If our strings array contains only unique strings, then this frequencies object is going to contain all of them. So it's essentially going to be proportional to the size of our strings are a meaning. It's also going to be oh, of end. What can we take away from this problem? Well, this problem essentially forces us to store an update data as we go through our loop. This is a good technique to keep in mind. Problems often won't require this, and a solution can be reached without keeping track. In fact, even here we didn't have to do this. We could just comment that out and comment this out, and we could perform some post processing meaning down here. We could add a little more code to then figure out which value is the highest and then which string that corresponds to. But instead we keep track of everything as we go through our loop, so we don't need to do anything afterwards. In general, try seeing. If storing data and some creative way can make an algorithm easier, it might be able to reduce time complexity. But if not, at least it can make the code simpler. We'll see in the next video
10. String Rotation: welcome to the next problem. String rotation. The goal here is to write a function that will take in two strings and determine if their rotations of one another. Now what's the rotation? These are examples of rotations, so we have the string 1234 To rotate it, we can take a character off the beginning and place it at the end. That gives us 2341 We can do that again and take the two and move it to the end, and we get 3412 and doing that one more time. Moving a three to the end gets its 4123 That's a rotation here. Some more examples. Let's go ahead and start writing this function, so the very first way we can find out if they're certainly not rotations is if the strings have different lengths for two strings three rotations of another of one another. They have to be the exact same length. So let's go ahead and check that. Okay, done with that? No. One way we can solve this problem would be to take our first string and create every possible rotation of it as we do that. We'll check if those rotations equal the second string. If they do, we can return true. And if we get through all the rotations and there aren't any matches than we can return false, let's go ahead and write a loop to do that for us, and to do so, we're going to use the string dot sliced method. This is a method that will extract text from a string. The way to use it is we give it to parameters the start and end index that we would like cut out and it'll slice between those two indices. So, for example, slicing this at Indices one and eight means Index one is right here and next eight is right here and we'll get everything in between those two. Meaning this this is the method will use. Let's see what in this prints out and let's go ahead and get rid of three of these and focus on this one. Okay, So as I moves from left to right, we get slightly larger and larger slices. Now let's try to other indices. Let's try slicing. We did from the beginning to the index, and now let's try in the index to the length of the strings. And what we see here is a perfectly clean split. What we need to do to actually rotate this string, its place, this at the beginning. And then we would get rotation with an R at the end. We keep doing that and putting this string before this one, and we've generated every possible rotation. Let me show you what that means. We just need to switch the order of these two and we get every single rotation one by one of letters. Take it off the beginning and placed at the end. This is exactly what we on we need to do now is check. F rotation rotation is equal to the second string. If it is, we can break out of the loop and return true. And if we get to the end and none of them match, we return false. Let's go ahead, get rid of these and see if that works. So we expect to truce and two false is, and that's what we get. We're looking good. Let's talk about the time complexity of this function. So we already have a loop here, bringing us to Ole of Ed this time n isn't the size of theory a or the number of arguments . It's actually going to represent the length of thes strings because that's pretty much the only thing that changes. In fact, that is the only thing that changes that we can measure. So we have a no of end loop here. Let's inspect this line this line a little closely. So slice, according to the docks for Indian, is actually a loop because each character has to be contaminated one by one. So believe it or not, slice is an O of n operation. And what we have here is a loop within a loop bringing us to, though of n squared and space. We're storing a rotation and this variable, so the amount of characters in the string that this variable holds is going to be equal to the length of the string. So, in other words, the amount of space this variable uses up is going to be equivalent to the amount of space that this string uses up. So that's going to be linear. That's it for the solution. But there's one more that makes this a lot simpler for us. I'm gonna go ahead and write the code out and we'll discuss it immediately afterwards and let's run it and we're good to go now Let's think for a minute why this is working. Let's take these two and let's place rotation next to itself. So in other words, we're performing this action right here. Str wana plus str one And we're checking to see if this if this string so the very 1st 1 duplicated has the 2nd 1 somewhere in it. So we're looking for the existence of this somewhere inside this and we can find it. It's right there. Try it out for yourself. But every single rotation you can come up with will be present in this string. That's pretty much a law here. In terms of how these rotations work, you put a string next to itself and it contains every rotation of the initial string. The time complexity of this solution is oh, of n. All we're doing is adding a string to itself, which is linear and then checking to see if it includes the 2nd 1 which is also Lanier. So that turned into oh, off and space is also of n because we're adding these two and the length is going to be proportional exactly. Double to the length of this one right here. That's it for this problem seeing the next one.
Arnav Aggarwal, Full-Stack Engineer & Instructor
