C++: Preparing The Coding Interview

1. Welcome to this course! : Hello guys and welcome to C plus blast programming. The coding interview. My name is Alex and time of an experienced software developer that has been working with C plus plus for about four years. Now, the structure of this class is going to be split in key elements that are discussed aim document called interviews for software developers. First of all, we are going to talk about the complexities of an algorithm, both time and space. Then we will jump into arrays. Then we will look at strings. Then again, interview questions based on strings is the topic that we are going to concentrate on. Then also, we will look at a few very important sorting algorithms like bubble sort, quicksort and so on. We will also look at trees. They're traversals, and a few other interview questions that you can receive on DOM. And also, we will take a look at stacks and queues. The class is created for any party that either once to learn algorithms in the programming language of C plus plus, or someone that wants to get employed in the field of software engineering. And once you learn questions that can be given on interviews so they can base their interviews. There are no actual prerequisites for this course. Then your willingness to learn and an Internet connection. As far as the class project goes, it'll be a question that can be received in an interview scenario that you can look at. Think about the head, may be time yourself for 30 minutes and try to come up with the best extract that you get. So it called that sounds interesting. I look forward to see you in the next lesson. Let's get started. 2. Big O Notation: Welcome to Section two, big O notation. In lecture one, we are going to talk about big O, big Omega in time complexity. Let's get started. The big O notation is a mathematical notation that describes the limiting behavior of a function when the argument tends towards a particular value or infinity. In computer science, big O notation is used to classify algorithms according to how they run time or space requirements grow. As the input size grows. Not understanding it thoroughly can really hurt you in developing an algorithm. Not only might you be charged harshly for not really understanding Big O, but you will also struggle to judge when your algorithm is getting faster or slower. When analyzing algorithms for efficiency, we use big O. For example, the time, the number of steps it takes to complete a problem of size n might be found to be n times n to the power of two plus eight times n plus one. As n grows large, the n to the power of two term will come to dominate that. All other terms can be neglected. For instance, when n is 500, the term five times n to the power of two is one hundred, ten hundred times as large as the two times n. Ignoring the letter would have negligible effect on the expression's value for most purposes. Further, the coefficient became irrelevant if we compare it to any other order of expression. So the big O notation captures what remains. We write o of n to the power of two. Now, let's look at some examples of the time complexities that certain computer science algorithms. One is called constant. For example, an algorithm that determines if a number is even or odd would have this time complexity. O of log n is called logarithmic. For example, searching an element with binary search in a sorted array. I will present these types of search and how it works in a later section of n is called linear. This is the time complexity of iterating through an array for a variety of purposes. For example, to find an element and so on. O of n to the power of two is called quadratic. This is the case when you have two nested force in an array. This can be useful when you want to sort an array. Finally, o n factorial is called factorial. And we run into this time complexity when trying to, brute force solutions are calculating unrestricted permutations. In general, encoding interviews, you enter time complexity to, though as you can, for your algorithm to take less time to execute and be more efficient and optimize. However, you can start from a solution that is not that great if that is the first idea that you get to solve it and then work your way to a more optimized approach. Academics use Peek, oh, big theta and big omega to describe runtimes. In academia, big Omega is the equivalent concept, but for lower bond, printing, the values in an array is big omega of one. After all, you know that it won't be faster than this runtime. Big Theta gives a tight bound on runtime. We can say that the bonding of function from above and below is represented by theta notation. The exact asymptotic behavior is done by d Theta notation. In this course, we will use just the Big-O notation for our algorithms in the way that industry tends to use it by always trying to offer the tightest description of the runtime. 3. Array and vector overview: Hello there and welcome to section three arrays. In this section we will talk about a basic data structure named erase that comes up a lot in interview questions on coding. And it's very important for you to have a good grasp of it in programming. When we think of an array, we think of a data structure that resembles a collection of items, stored memory locations. The idea is to store multiple items of the same type together. This makes it easier to calculate the position of each element by simply adding an offset to a base value. Example, the memory location of the first element of the array, generally denoted by the name of the array. The base value is index 0, and the difference between the two indexes is the offset. For simplicity, we can think of an array fleet upstairs where on each step is placed the value, let's say one of your friends. Here, you can identify the location of any of your friends by simply knowing the account of the step they are on. Remember, location of the next index depends on the data type that we use. And it says, by default, regular arrays of local scope. For example, those declared within a function aren't left uninitialized. This means that none of its elements are sent to any particular value. Their contents are undetermined at the point theory is declared. But the elements in an array can be explicitly initialized to specific values when it is declared by enclosing those initial values embraces. For example, you can see here the first line in our image. The number of values between praises shall not be greater than the number of elements in the array. For example, in our image on the first line, was declared having five elements specified by the number in close the square brackets. And the praise is contained exactly five values. One for each element. Declare it with less. The remaining elements are set to their default values, which for fundamental types means they are filled with zeros. The value of the elements in an array can be accessed just like the failure of a regular variable. The same type. The syntax is name and then in-between brackets, the index. Notice that the third elemental Fu specified F-O-O. Then in brackets the number two. Since the first one is F0 of 0, the second one is F0 F1. And therefore, the third one is f o of two. By the same reason, its last element, It's F0, F4. Therefore, if we would write something like F0 05, we would be accessing the sixth element of F-O-O, and therefore actually exceeding the size of the array. In C plus, plus. It is syntactically correct to exceed the value range of indices for an array. This can create problems since X is in outer fringe elements do not cause errors on compensation, but can cause errors on runtime. This point, it is important to be able to clearly distinguish between the two uses that brackets have related to erase. They perform two different tasks. One is to specify the size of arrays when they are declared. The second one is to specify indices for concrete array elements when they are accessed. Do not confuse these two possible uses of brackets with arrays. At some point we may need to pass an array to a function as a parameter, C plus plus. It is not possible to pass the entire block memory represented by an array to a function directly as an argument. But what can you do is that you can pass instead its entries. In practice, this has almost the same effect and it is much faster and more efficient operation from this base point of view. To accept an array parameter for a function. The parameters can be declared as type, but with empty brackets are meeting the actual size of the array. For example, for a procedure. And then in the parameter list, int arg. Then some empty brackets. This function accepts a parameter of type array of int called ARG. In order to paste this function, an array declared as int, my array elements, it would be enough to write a code like this procedure of my array. So this would be an overview of the array type in C plus plus. Of course you can do many more operations with each of the elements. You can swap them and so on. Next, in the coming lectures, we are going to take a look at a variety of algorithms that very oftenly come up in coding interview questions. And we will look at their complexity, different approaches, and basically how to solve them so we can better be prepared for your future interviews. 4. Deleting in an array: Hello guys and welcome to lecture three, deleting in an array. In this lecture, we're going to talk about how to delete an item from an array. This question has two variations. From an array where we know what the value of the number that we want to delete from the array. And the variation where we know what is the position of the item in the array that we want to delete. Right here we have the variation where the value of the item is entered and not deposition, but the other one is very similar to this one. Let's run the code and after debt and some explanations of it. We can think about the complexity of this program as we would do in an interview situation. Let's start from the mean. As a good practice, It's always good to separate your functions from the main function and then call your function that you wrote for a specific question from the main function. In an interview question and an interview scenario, they might even give you the function without the body. So it's just a header. And then you write the function that should do how that started the SQL for. In our situation, as we entered the main function, we declared our int array that we are going to remove from, initialized it with some hard-coded integral values. Then we got each side dividing the size of theory by the size of an integral. Then we wrote x is six. We wanted to remove six from this array. Now, we will call the delete element function, which returns the new size of the array after removal, and also obviously removes the item from the array. This delete element function, as you can see, it has three arguments. The first argument is our array that we want to remove the item from. The next item. The item means the size of the array. And the last item is the number we want to delete from the array, in our case six. And as you can see, this is the arguments that we pass when we call the function. What this function does is it declares an i variable used to iterate through the array. And then in a for-loop, we iterate through the whole array, taking each element. And if the element is equal to x D element that we want to remove from our array. Then we break. X is found in the array and I is the index where x was found. We are going to decrease the size of the array because it is going to be one size smaller than it was before, because obviously we are going to delete an element from it. And then we're going to just move all the elements one space ahead. Lesley, going to return the size of the array. Here is the new length of the array. Then we are going to see out Monte Carlo and then iterate through it and show it. So if we run this, we are going to see the tower new array should be 1158910. You can see that's the array. So now let's think about diamond space complexity. The space complexity is obviously linear because we don't declare any other variables. If we do, they are considered constant. This space is linear and then the time complexity, well, we iterate through the array once here. And obviously once here. The time complexity is linear as well. Can we do this in a better complexity than this one? Well, no, because our element can be the first one, then it would still be linear because we need to iterate through the whole array. At this step. This was about deleting an item from the array. And you guys can do the variation where you delete an item from an array where you know the position is very similar to this one. But you can try that at home. And let me know how it went. 5. Linear search in an array: Hello guys and welcome back to lecture four. In this lecture we're going to talk about search in an array of integers, more precisely linear search. The scenario is that we have an array of integers that has numbers that are not sorted. So any kind of numbers that are integers. And the problem with S gas to find one number from this array and return its index. Now, we would obviously write a separate function from the main function that we call, would call from the main function and use that to find our element. As you can see in my code right here, we declare than a rate, it's hard-coded, values 2341040. Then the x value that's there. Then we are going to, as usual, use the size of helper function to calculate the size of our array. Then we are going to give our int, which salt the value of the search function. This function returns an int and it takes three parameters. Our array, the size of our array, and the number we wanted to find. Then going to iterate through it with the help of this auxiliary variable called. While we loop through it, we find our needed element, then we are going to return its index. At the end, we're going to return minus one, which means we didn't find it. Return i, as you already probably know, but I will remind you this. Tell you if you do not know, the return statement when you sit in your function, stops that function and it basically goes to where the function is called and returns that value. So what's after a return that's been heated? Function will not execute. This return minus one statement will only be heat if this return is never executed. So if our value was never found in the array, the result with the index of the value from the array that we want to find. If result is minus one, of course, going to say that the element is not present. And if it is going to say that it's present at the index result that's returned from our function. Right now, as you can see, if you run this program, we're going to see that element is present in index three. You know, the counting in an array is zero-based, meaning that the first index is 0. That's why this one will be one to n. The number of research for Dan is index three. Now let's speak about complexity. The space complexity is the size of our early, which is linear in regards to the input. Then the time complexity, well, the time complexity is given by our function because right here we iterate through our array once. That means linear time complexity. Now, can we do this better than linear? Well, no, because at worst case, the element that we want to find this position and that means we have to iterate through the whole array to finally find it in the last position. And that would take linear time. In this problem, both space and time complexity is hardly linear. Let's move on to the next lecture, where I will show you a more efficient way to do this. But under a condition, and that is the array being sorted increasingly or decreasing. 6. Binary search in an array: Hello guys and welcome to lecture five, binary search in an array. This is basically the first more serious algorithm that we are going to approach in this course. And this one is more often given in interviews. And maybe not these basic variation, but other variations that can have other constraints or not asked you the ceaselessly to implement this. But another type of problem where you need to use this type of algorithm. The problem is that given a sorted array of n elements, you should write the function to start to give an element x in this array. A simple approach, as we have seen in the last lecture, would be to do linear search on your array. The time complexity would be linear, as we saw in this space complexity would be linear. But another approach to perform the same task using binary search and given the fact that our array is sorted already. So what binary search basically does, instead, it searches a sorted array by repeatedly dividing the search interval. Inhale, begin with an interval covering the whole array. If the value of the search key is less than the item in the middle of the interval. Narrower the interval to the lower, help, narrow it to the upper hand. Repeatedly check until the value is found or the interval exactly. The idea of binary search is to use the information that the array is sorted. Reduced the time complexity, logarithmic one. Now, if we look at this picture, we can see an example. We have this array that has 2581216233856172091. We are going to take m in the middle would be low and it would be 0 and h would be nine. The three indices we are working with, we need to search for 23. Well, we are going to check, and 16 is smaller than 23. So we are going to move to the right. We are going to take l, m, the arithmetic average of n and h. And we can see that 23 is smaller, 36. Going to search in the left half. And right now would be six, because it will be m minus one. M would be five. Right here we searched for 23 without even looking at items like 5812 or even 72. Now let's look at the code and see how it works. The main function is very resembling of the last main function that we use on linear search on an array of integers. The only difference is that function that it uses and returns the indices where our number was found. This binary search function, as you can see, takes four arguments. The first one is our array of integers. The second one, the third one is the R. Or in the case that this picture would be h. Because right here is right, there was high. They mean basically the same thing. And then x is the number that we went to search. We are going to make recursive calls. Going to start by saying, aren't so right is bigger or equal to L. We're going to declare meet in the GRE and give it basically the average of R and L. If you are asking yourselves, why isn't this L plus R divided by two? And it's written like this. Well, this firstly does bear minus l and then add. This helps avoid cases of overflow. Number is big enough to exceed the memory and for your program will basically to crash. If array of meat was equal to x, the number we weren't searching for, then we should return the index because we found it. If it's bigger than the element we are searching for, then we can only look in the left sub-array. So we are going to recursively call binary search of ARR Again L. And then instead of area I'm going to call mid minus one, we are going only to look in the left sub-array. In the other case, we're going to look in the right subarray by giving the recursive call instead of l In the second argument, mid plus one. Lastly, if no other return was hit when returning from the recursive calls. Now going to return minus one. As you can see, if we run this program, number ten was found again at index three. As I have said before, the space complexity is linear because we declared the array, then the time complexity is logarithmic. Thanks to this nice algorithm. If the array is not sorted though, you cannot find an element in a better time complexity than linear. This is only made possible here because we know the array is sorted and we have this way, quicker way to look through it. This is about binary search. You can try to implement it on your own without looking at this algorithm. This is an important interview question and an important algorithm that you should really know very well. 7. Strings: Hello guys and welcome back to section four. In this section, we are talking about strings. Strings are objects in C plus, plus the three present sequences of characters. The standard String class provides support for such objects with an interface similar to that of a standard container of bytes. But I think features specifically designed to operate with strings of single-byte characters. Here we can talk about member functions like swap, that swaps the content of two strings, append, that appends a string to a given string and returns a pointer to the resulting string. Inserting, erase, find some SDR and many others. I will attach a picture here with descriptions for each of them so you can read them and understand what each of them does. We can also talk about overloaded operators, such as a bending of two streets. They stand with the plus equals sign concatenation, this time with the plus sign. The equality operator, implementing through to equality signs and so on. This glass also has a variety of constructors. The empty one that creates an empty string. The one that takes as the argument, the string in-between brackets. You can write your string and it will initialize that drink object with the stream that you right there. The one that takes an integer and a character and instantiates the string with that character that will be repeated by the given number of times. To use strings, you must include an additional header file, illustrators code that will be include. And then string dot h in-between triangle parentheses. Also, you saw that you might include iostream that comes from input, output stream, and you usually need to write and read keyboard input. Note that this class handles bytes independently of the encoding, is used to handle sequences multiplied or variable length characters, such as UTF eight. Members of this class, such as length or size, as well as its iterators, will still operate in terms of bytes, not actual encoded characters. In the next lectures, we're going to take a closer look at some interview coding questions that might come up that use strings. Let's get to work. 8. Concatenation and finding the length of a stringConcatenation and finding the length of a string: Hello guys. In this lecture we are going to talk about contact nation and finding the length of the street. Let's start by talking about concatenation. The plus operator can be used between two strings. Do I add them together and make a new string? This is called concatenation. Let's treat it in C plus. Plus is actually an object, as we've already talked about. In the last lecture. Nice object contains functions that can perform certain operations on strings. For example, you can also concatenate strings with the append function. You can do these in whatever way you prefer to. Talking on a more concrete level. You can see in your code something like string S equals to a plus b, where a is another string and B is also a string. And concatenate them by making this twin of a and B at the end. And it will basically make one is three, contains both of them first day and then B. Now to get the length of a string, you can use the length function has deep. You might see some C plus plus programs that use the size function to get the length of the string. This is just an alias that blank. It is completely up to you if you want to use length or size. Now of course, if you wanted to implement this problem without using these pre-built function, it will be pretty simple. You will have to iterate through each character of the array with a for loop and then have an integral instantiated with 0 incremented for each character. That way you can get the length without these pre-built functions. You can access the characters in a string, as you would in an array of cars by referring to its index number inside square brackets. To change the value of a specific character. String, refer to the index number and use single quotes, because that's a character. 9. Changing case of string: Hello there. In this lecture we are going to talk about how can we change the case stream. The problems here is that we need to convert all the uppercase letters to lowercase and vice versa. Industry. New approach here would be to iterate the string and use the ISA per pre-build function to determine if each character is in actual application or not. If it's uppercase, we will convert it to lowercase using the CO2 lower pre-built function. And if it's not uppercase, converts it to uppercase using two upper pre-built function. Now, we can also do this without these pre-built functions by adding or subtracting the value 32. Because that's the difference in numbers between an uppercase and lowercase value. For example, the letter uppercase has an ascii value of 65, and lowercase has an ascii value of 97, which is 65 plus 32. You can also use this little heck to do this problem. If the interviewer specifies that you are not allowed to use any pre-built string functions. Now, if we look at the code, we have this main function where we declare an STR stream, also specifies the std scope because we didn't use using namespace std. So you can either write the using namespace std or say std. And these two double dots before Amy, STD member that you write. In the next line, we initialized STR string with this string right here. And then we call the transform function on this STR with using three iterators from beginning of the SDR string to the end of the history or string, then we aren't going to breathe in March called The Change Case for each character of it. This is just a way to iterate through it. At line 16, The Change Case functions takes a character and it returns a character, as you can see in its header. And it's just an if function that verifies if the character is uppercase, then it returns the lowercase. And if it's not means that it's lower case. That case we are going to return the upper case character cell after we transform the whole string with this function, it will pretty much every first Casey. Then we are going to write it on the output command prompt. And as you can see, if we run this code, we get the exact string that we initialized reversed case. I've already said you can use the 32 little hack to do this problem without any built-in functions. 10. Counting words/vowels: Hi guys and welcome back to lecture four. In this lecture we are going to talk about how you can come towards the vowels in a string. Basically a bigger string that has spaces in between words. Something like samples or Pablo's can be if an award. What the problem sounds like is that the function that you are supposed to write receives an argument that's a string, and then you need to return the number of vowels. For dinner of words. This is the problem we're going to talk about today in this lecture. As you can see, I already coded it up for you, but we are going to run, as we usually do. Commend, going to discuss what everything basically does is usually we start from the main function. Here we declare a string that I called SDR and Nike feet ABC space. And now we have two functions to count the number of values it has. First function receives the third character, returns brilliant. What it does. Thanks this character. Uppers. For example, it would be a lowercase. It return it to uppercase. We can verify against the upper teeth spotless and not the lowercase too, because then we would have had five conditions here with the OR operator between them. What we do is return there, the character. Character. Character is a character like this, E, I, O, U. Any of these seats true? Then we return to this function. As you can see, it's called from another function is called count vowels. This one receives a string parameter based TR. Initializes and integrate, count. The value 0. Then we iterate through the string, through each of its characters. Then if the dead character vowel, then we up the account. At the end, we return it. This is a very simple method to return the number of vowels string. Now let's talk about the complexity of this algorithm. Well, first of all, this space is linear because we don't declare more than this treatment itself. Then the time complexity is linear to, because we iterate through each of the characters from the string, both time and space and place. These are linear big O of n. Now, moving on to the next problem, going to count the words. That's going to do this by writing a function that receives from parameter that's a stream and then returns an integer. Clara Decker, now that we initialize with 0 and a character that we call preform previous death initializes with space. Now we eat the way through the stream that we receive as the parameter. If the current character space in the previous lesson, we increment. Now, what does this mean? Well, it means that we found the beginning of a new word because the character, now it's not the space in the previous space, used to be a new word, one. Lastly, we're going to update previous with x of i. When we look in the next iteration. Current, previous, hence the actual previous bear. Decent orientation. We are going to return the number now. Thanks, you can't see. If we call this function, it returns two. Because our string ABC space D0 would be considered to have any abc. And then these are not actual words. But if you're typing a sentence that we didn't make sense, it would be worth. Now talking about the complexity of this algorithm, I think it's pretty clear that this space is in regards to the input, because we don't declare anything more than the stream itself. We have linear space complexity, time complexity. It would be linear as well because we eat the retarded once through the stream to check the condition and the previous value. Right here. We discussed two basic algorithms that come up. A few questions. Starting problems. They are very basic, but it's very important to start with the very basic ones in understanding the complexities and how to do them optimally. Because you can then build upon the foundation, depth. You have to solve and understand more complex algorithms and problems in the future. The next chapter we're going to talk about have to reverse a string, which is a more commonly met interview question. 11. Reversing of a string: Hello guys, welcome back. This lecture, we're going to talk about how to reverse a given streak. How are you going to do this? Problem says, is that given this gene from input, from keyboard or a file, you just give it the value I hard-code the task matric Jeff tapestry, and the problem is to reverse it. So for example, if we have a string, if your function with ideally we tend to stream refers to the debt would be reversed order. Not going to discuss how we implement this function and what its complexity each cell, first of all, we declared a string. It says Welcome to the squares. Then we just call this function on. This function doesn't return anything. It's a void return type function. We initialize the length of the stream, then we iterate to the health of the stream. What we do is we swap in-between them, the matching characters. For example, when I see or we are going to swap these T-R-I-E tasty r i n minus u, o minus one, minus one. Because zero-based counting decent arrays, we're going to talk to swap the first element, which is 0, element which is minus one, a zero-based. For example, the string. We're going to take intent G minus one. It's going to take the one indexing then n minus two, which is then swap them and then swap them. Points. We heat the middle of the street, we stop. This is basically the most optimal way to do this operation. And this, you can see if I heat, we are going to receive these gene in reverse. Now, let's talk about space complexity of this algorithm. First of all, this space complexity is linear regards because we don't receive the time complexity. N divided by two, because half of the array stop matching characters in-between them. As we know, only the n and its power. The Big O notation of time complexity would be, as well as the space complexity be linear to this algorithm. The next lecture, we are going to see how manage to check if a word or a string is a palindrome. Benadryl, meaning that this dream that you have first is the same. Let's move on and talk about how can we do that. The complexity of that algorithm would be. 12. Checking palindrome: Hello guys and welcome back to the course lecture. We are going to see how can we check if it worked? Meaning a string is a palindrome means that it's the same. It's the same if we read it from left to right. For example, a BBA would be a Benadryl because probably it would be ABB form. That would be still a BBA. This one would be a bit of drama as well, but these ones wouldn't be because we read it from left to right beyond the half-life, the beginning. Repeat from right to left. We have two LC WE. Now that we have understood what the problem is, you would do an interview. The first step is to understand what the problem once from you. We can think about how to solve it. But since we just talked about how to reverse a string, this is a very similar problem in these very easily done if we have the reverse algorithm, because we would just need to check if our stream would be equal to the reverse of it. With p equal, it would be probably true. But now we are going to take another approach to this problem. Solve going to function as a parameter string. And then we are going to not return any degree because you are going to just imprint on the output this gene that receive as a parameter. The parameter is going to start off by initial values 0 and then age with the size of our stream. Then, while index, index, index, this case XDR of not equal to the STR. So the magic character from the beginning, not the scene we are going to print. The string is not apparent. Draw me the return to function h and del cross paths. Meaning that age is not inverted, means that the whole stream, we can draw this. You can see if I drag, it checks out for each of these tricks. So a BPA, a BB, CC, BB or not. Complexity. Complexity easily regards today in, but because we've got this napa constant other than the input stream, would be the case, is two divided by two because we all need to have this gene. We reached half of h would be the while loop with IT. Complexity is linear instagram regards to the precise, these would be obviously topo stopped him away to do it. Because you still have to check trough of theory to make sure all the characters are equal so that you can confirm that your students about in the last lecture of this section, the next lecture. We are going to check if two strings are anagrams, meaning post the same characters. There's more. See how can we do to be the most optimal algorithm. 13. Check if 2 strings are anagrams: Welcome back. In this last lecture here talking about how can you check given strength? Words? They can be sentences. Meaning they are composed of characters. What do I mean by sample? We have two words, such as dog. Dog would be anagrams because one T1, 01. This would be an agreement anymore because the count within these run with f one g, and this one we have two G's anagrams. The problem asks us to write the function to check if two strings are or are not anagrams. So as you can see, the main function we start by initializing each of these strings. We are calling a function that takes as parameters two streams will be true. If this G is I integrate cosine function, we declare two integers that links. We are first going to check the strings have the same length. It means they can't have the same characters. Because obviously two amounts of characters can't be equal before the speaker TPI out, they're going to sort strings. The stars, sort them based on ascii values, sort them in alphabetical order. Then we are going to be three genes at the same time. Did here we use then one, but we could have used because basically the same. We wouldn't be in this function, this line because it could hype already returned false boolean. We iterate through each of these genes and we check their character, say equal, not equal, we return false. We reach the end of them instead, talk characters are equal and we can return true. We put this function that returns each state one to ten. We can these streams, grams will be charted. It otherwise we can say that they are not. For example, if we see these two strings, the right sample, you can see that they are n. If we change the second stream, what it would do is basically with this condition, be a false or we can even make them the same size, different letters and the two, it's still black patients you can see right here because they would sort them in alphabetical order and see that one is p, one is G. Best this if statement trend here, three times false. Now let's talk about the complexity of the program. Saline regards space complexity. We can consider the first streaming. Space complexity would be big O of n plus m. Thank you guys for staying with me. In this section. We are going to continue with the next section. Very important topic regarding the interview coding questions. Sorting. Either if we talk about the nursery or as you can see, it can be very useful when we work with strings. So we're going to cover up their complexities section now. 14. STL sort() function: Hello guys and welcome back to lecture two. In the second lecture, we are talking about the sort function that's available in the standard library of C plus plus. You can use as an easy alternative when the interviewer isn't actually trying to test your ability to sort an array or some data structure, but it is required in order to do the rest of your problem. You can try to use these sort a function. And it's a scenario where you need your items sorted, but you don't need to actually implement the whole algorithm by yourself. Sorting is one of the most basic function supplied data. It means obviously arranging the data in a particular fashion, which can be increasing or decreasing or whatever else comparison function you might use depending on the data structure that you have. In more complex environments. Suppose you have structures of type cat. You want to order them by the number of whiskers they have. You will need to implement this specifically comparison function. You can actually pass third argument to this function. We will see that later. It will sort them basically by number whiskers. There is a built-in function. As I've already said, the C plus plus STL comes from standard library. Name of this function. Internal uses interests are in more details about each implementation because the interviewer might even SQ, how these function implemented if he sees that you use it. Well, it using a hybrid of quick sort, heap sort, and insertion sort. Depending on a few factors. By default it uses quicksort. What if quick sort is doing unfair partitioning more than n log n time? It switches to heap sort. The array size becomes really small. It switches again to insertion sort. Now, if we take a look at this code right here, we can see this function right here in action. You can see in the main function we looked at unary that we initialized hard-coded array. Then we got size using the size of operators. Then we use this function right here that takes two iterators. So we gave it ARR, which is the pointer of the first element of the array. Then ARR plus n, which is the end of the array. Then it sorts it. To see it in action. We also printed it on the screen after sorting and as you can see right here, sorted it increasingly. Now as I've said, your kin past this sort function, third parameter of comparison that would order the elements in a different fashion. Show you this. I will keep this sort function, parameter, comparison function that sorts the elements decreasingly. That's called greater beat. It altered our decreasingly. We can of course, implement your own function right here that you can write yourself above the main function that takes two parameters and returns a boolean on whether whatever condition you want to reorder is true. This year would be very interesting and easy way to bypass sorting in an interview. As I've said, if the interviewer is that debt, curious to see if you can actually sort the array yourself or S2 for a specific sorting algorithm. Also, given time complexity by its implementation, it's n times log of n. And that's actually the best complexity by which you can order an array. Now, in the next few lectures, we are going to take a closer look at some sorting algorithms that are actually implemented. The way that they work. Also, we will look at their complexities. See a few ways to sort an array or another data structure that you might have. 15. Bubblesort: Hello guys and welcome back to lecture three. In this lecture, we will talk about the most basic algorithm that sorts an array that you can implement by yourselves very easily. It is called bubble sort. It doesn't have the best time and space complexity. But we'll get to that in a second. First of all, I have to say about this algorithm, besides the fact that it's the simplest sorting algorithm exists, how it works is by repeatedly swapping the adjacent elements if they are in the wrong order. So now let us look at this example so we can visualize better than by looking at the code. How is the way that the algorithm is actually white cell? We are going to take the array 5142 into what it does. Basically paid first two elements. And it sees that five is bigger than one, so it swaps them. Then it takes 545 is also bigger than four, so it swaps them again. Next, 525 is bigger than two, so it swaps them. And at the end we have 58. These are correctly position, so it doesn't make any swaps. Then it passes again. Taking elements two-by-two, as I've already said, adjacent elements, paraphrase them if they're in the wrong order and if they are, swaps them, if not, it doesn't. One in four are in the correct order, so it won't swap come for him to or not in the correct order because four is bigger than two, so we will swap them. 45 are in the correct order and then 58 are in the correct order. Again. You can see at this point our array is already sorted, but our algorithm doesn't know if it is completely sorted yet, because it could have not at this point. So it needs another hope is that it won't swap obviously any elements because they are already or third sending. But as you can see in the third base, it takes again the elements Dubai, and it doesn't make any swaps. Now, let's look at the code for this algorithm. As you can see in the main function, we are declaring is usually a hard-coded array with some values in it. Next we declare an integral, and this time to eat the size of our array that we declared, making use again at the size of operator. And then we are calling the bubble sort function. That as you can see, it takes two parameters, our array, and it's now moving up in stack. You can see that it enters the bubble sort function. It returns a void because it just sorts the array and doesn't return anything. For the first element takes the array in this, I've said, the second element is the size of it. Now we will declare two elements, I and j. Theta. I'm just used to iterate through the array. It goes like this. Query. Each element of the array, we will go again from 0 to n minus I minus one. You can ignore because it is zero-based. It basically goes from the first element of theory to the n minus item. And then it checks if ARR of j is bigger than ARR of g plus one. Which means that we have a bigger element that is before a smaller element. And we cannot have this SP1 to our array in ascending order. Swap the addresses of elements located at, before said indices. Display making the change pregnant. And when we return to print the theory, you can see that when we run the program prints the sorted array increasingly with the fact that the second loop on the iterates to n minus I. There is a reason behind that. Because the array elements after n minus I already sorted. Because if we think about it, first, it goes I goes from 0 to n minus one. So the end of theory in the second loop goes from 0 to n minus I minus one, which is also n minus one. So it goes to the end. It keeps the chance for the last element to be at the last position. Next, iterate from 0 to the last element. And then the chain element will iterate on the two n minus one minus I, which will be one, that's n minus two. So excluding the last element. Basically it will search the second biggest element from the array and so on. That's how the algorithm works. It continuously thirties, where the biggest element to put it at the end of theory. By the end, I understand the end is not already sorted. The first iteration, it will search for the biggest, biggest element. The second iteration for the second biggest, and so on, reaches the first element in the array is already sorted. If we were to talk about the time and space complexity of this algorithm, the space complexity is linear in regards to the input because we just declared this array right here, and then we declare two variables, iterating three, but that are considered constants. So the space complexity is big O of m and it is linear. Now getting to the time complexity of this algorithm is big O of n to the power of two. So it's a quadratic time complexity as the algorithm iterates for each element of the array. Another iteration to basically not really to all the ray, but you get the idea. It tends asymptotically to a quadratic complexity. Now again, we have a swap function that I didn't even talk about. What this does. As you can see, it doesn't return anything it takes to integrate pointers and it swaps between them. That's a very quick and simple sorting algorithm that you can use on a race that you wanted to sort English increasingly. But just know its time complexity is quadratic and not the best type of time complexity that you can have when sorting an array, which would BASF already said n log n. So if we propose to implement this algorithm now that it's not this time complexity, as you can see in the next lecture, there are better sorting algorithms out there that you might learn and actually implement during your interview when being asked about it. But it's a foundation. And this is a pretty basic algorithm. It's nice to first make contact with an easier sorting algorithm to get it started. 16. Quicksort: Guys, welcome back to lecture four. In this lecture we will talk about Quicksort. Quicksort is another sorting algorithm that works on arrays. And it's more efficient algorithm then propose sort From the time complexity and space complexity point of view. Now, unlike March toward, quicksort is a divide and conquer algorithm. What it does, it just big element and partitions the given array around the pivot. Many different versions of quicksort, that big pivot in different ways would be to always pick the first element is. Another way would be to always pick the last element, this pivot, as we will do in our implementation. You will see that in a second. Then you can pick a random element is period. The best way would be to pick the median SPM it. The key processing quicksort is partition. The target of partition. Given an array and an element x of array pivot. What this partition function does is that it puts x and its correct position in an array, meaning that all the smaller elements then it would be on its left. And all the greater elements then it will be on it, right? On this process should only take linear time complexity. We look at the code and try to understand it. We are going to see that in the main function we declared an array as we always do this hard-coded values. Then we take its length using the size of operator. And then we call a function called quicksort that takes three parameters. The first parameter being the array. The second parameter, pink dots over bound to that you want to sort, in our case, first element index, that being 0. The last element, that third parameter, the upper bound that you wanted to sort in our case, the last element index, and that is n minus one. We also declared a couple of oxygen carry functions. One of them printing theory. The second one is swapping two elements using pointers. Now, if we go to the QuickSort function that gets called from the main function, we are going to see, first of all, checks if low is smaller than this is done because later we will recursively call this function in the left and right subarrays of the pivot. So we always need to keep that in check that the lower bound is lower than the higher bond. Then going to give the value of perdition of our array. And lower and upper bounds being the partitioning index. Meaning, where is our pivot at the right position in the array that would be sorted. In this deposition that we just talked about. The position where all the elements in its left and smaller than him, and all the elements in it's bigger than him. It doesn't matter what their order is because the array sorted or not. It doesn't matter. That element is at the track position where that condition happens. And then we will recursively call this function our array, the low bound and pivot position minus one. And then our array pivot index plus one and then higher bound, meaning that we will recursively call quicksort for the left sub-array and the right subarray of the pivot that is correctly positioned at this point. Let's see what this partition function does. It also takes three parameters as the QuickSort function does. We declare a pivot. Integral takes the last element because as I've said, we will implement the variation of QuickSort where the pivot is taken as the last element from the array. Then we will declare I, which would be o minus one, minus one, because the first element of our array would be 00 minus one is minus one. We will see in a bit why we take it minus one and not 0. And then we will use another integral to iterate through the whole array. Iterating through the whole array. We say if ARR of g, meaning the current element from the iteration, is smaller than the pivot. First we will increment I, then we will swap ARR of I of j. Then we will move on these dyes, linear iteration through the array. And 28, we're finding an item that's smaller than our pivot. In this case, the last element of the sub-array we are at it, we'll put it in the beginning of the array. In the beginning, well, first index that's not already occupied. It puts all the elements that are smaller than our pivot in the front of the array. Then lastly, we will swap ARR of I plus one with our pivot. Because that's its right place in the array. That's where it would be wrong if the array will be sorted, we will simply return this index, that would be its correct index. Now, you can see we understood how the partition function works. And we also understood that after cold, we also called recursively this partition function on the left and right sub reason to pivot. This way, sorting the array. Now as you can see, we have an array of elements then 789, One, and five. When we run it. The printArray function should print our array. This, you can see these sort data. Now let's talk a bit about these algorithms. Stability respects are not in place. Property. First of all, is Quicksort stable? The default implementation is not stable. However, any sorting algorithm can be made stable by considering indexes as comparison parameter. Second of all, expert, the broad definition of in-place algorithm. Quicksort qualifies as an employee sorting algorithm. C2c is extra space only for storing recursive function calls, but not for manipulating the input. We can say that it has linear space complexity. Let's talk about the time complexity to really see how efficient this algorithm is. Well, even though it's better than bubble sort, which in the best time complexity would be linear. But in the average and worst cases would be quadratic, would be big O of n to the power of two. Quicksort pattern in the average time complexity, various n log n. The mask complexity is still n log n, but the worst complexity is still quadratic. N to the power of two. In interviews, name actually asks you something about weeks. If not the full implementation. You may ask you if you know what its time complexity, whether you know how to partition function works and what's its time complexity. Which by the way is linear. As we already saw. We only iterate through the array. And he might even SQ the recursive calls in quick sort function where it is a very good sorting algorithm in an interview. And it's a very useful tool you can use to sort the elements of an array that you have. When you don't have the STL sort function, bubble sort, bubble sort. If you would want something more efficient, then this algorithm would be a perfect match. 17. Trees: Hello guys and welcome back to section six of this course. In this section we will talk about the new data structure called threes. And unlike arrays, linked lists, stacks, and queues, which are linear data structures, trees are hierarchical data structures. The top node is called root of the tree. The elements that are directly under an element are called its children. D element directly above something is called its parent. For example, a is child of f and f is parent of a in this tree debt we drawn on the screen, right? Finally, elements with no children whatsoever are called leaves. Now let's talk about why would we use trees? Well, one reason would be because you went to store information that naturally pharmacy heirarchy. Think about how your files are organized on your PC or Mac book, whatever you have, the start from the root folder and then you go through them in an article order. Fast system on the computer. These probably implemented using trees. Also, trees provide moderate axis and search. That is curtain linked list, but slower than arrays. Tree is also providing moderate insertion and deletion. Quicker than arrays but slower, thinner, unordered linked lists. Also likely list. And unlike arrays, trees don't have an upper limit on number of nodes. Nodes are linked using pointers. So there is an advantage when we look at this page that a tree and you can store. The main applications of trees include manipulating hierarchy TO data, making information easy to search. We will see that it traverses, in one of the next lectures. Manipulate sorted lists data. They can be used as a workflow for composing digital images, for visual effects, router algorithms. And also the farmer multistage decision-making, for example, business chess. From an implementation point of view, the tree is represented by a pointer to the topmost node in the tree. The tree is empty, then the value of this topmost node called the root is known. A tree node contains following parts. First of all, it contains data in, then it contains pointers to its children. We can represent three nodes using structures. For example, I'm attached right here. You can see exactly what I'm talking about. But we will move on to implementation in C plus, plus that little bit later. Right now let's talk a bit more about what types of trees there are in programming. As I said, three in computer science is like in the real world. The only difference is that in computer science it is visualize this upside down with root on the top and prevent disease originating from the root to the leaves of the tree. Tree data structure is a non-linear data structure. A tree can be represented using various primitive or user-defined data types. As we saw with discharger just now. Implemented three, we can also make use of arrays, linked lists, glasses, or in other types of data structures. It is a collection of nodes that are related to each other to show the relation nodes are connected with edges. But in practice, more like heavy pointers to one another. The types of trees in data structures. First of all, there exists the general tree, which there is no constraint for it, imposed on it, on the air kept the tree. In general tree each node can have infinite number of children. These three is the superset of all other types of trees. Now, we will move onto binary trees that are much more useful in March, more about interview questions just because they have more simple and elegant structure and are easier to form questions based on. The binary trees is the type of tree in which each parent can have at most two children. The children are referred to as the f chart or a right child. Ntc is one of the most commonly used trees in certain constraints and properties are imposed on binary trees. It results in a number of other widely-used binary search G AVL tree. So on. We are going to talk about these types of trees right now. So binary search tree is an extension of the binary tree that we just talked about, but it has some other edit constraints. For example, the value of the left children of a node must be smaller or equal than the value of its parent. And the value of the right channel is always larger than or equal to the value of its parent. This property of the binary search trees make it sit suitable for searching operation. Intense. As it each node we can decide accurately whether the value will be in the exit to your rights. Therefore, it is called Search Tree. More complex type of tree is the AVL tree. That these are self-balancing binary search tree. The name AVL is given on the name of its inventories. Adult son felt shy. Then this is the first dynamically balanced tree that was ever implemented in APR tree. Each node is assigned a balancing factor based on which it is calculated whether the tree is balanced or not. If you have tree, the height of children of node differ by at most one. The valid balancing factor in if the arteries are 10 n minus one. When the new node is 80 to the AVL tree, entry becomes unbalanced, then rotation is done to make sure that the tree remains balanced. The common operations like look-up insertion intuition takes only logarithmic big of time in these AVL tree and it is widely used for lookup operations. There also exists some trees that are called the NRV trees. The maximum number of children they can have here is limited to this variable n. Binary tree is a tree, as you denote in binary today's most two children tree data structure, you find that the most common used in presentation of n. But full NRA trees, which children of a node is either 0 or complete enter retreat is the tree in which all the defaults are at the same level. For some properties of binary trees. Some more mathematical properties. We can say that the maximum number of nodes at level l of a binary tree is two to the power of l. Then again from its construction, the maximum number of nodes in the binary tree of height h plus two to the power of h minus one. In the binary tree with n nodes, minimum possible height or minimum number of Cs logarithm of base two of n plus one. Let's do a binary tree with LDFs has at least two l plus one variables. Also in binary tree where every node has two children, the number of leaf nodes is always one more than nodes with two children. This is a broad overview over the tree data structure. These are very useful in interview questions. Is the come up into more complex topic to discuss here. Many people I know including myself in the best was not so short on trees. But in this course we will look on some exercises with them, traversals and so on to make you feel more ready for your coding interview. Especially on these data structure. Then two problems do people, people who have been interviewed in the past. So let's move on to the next lecture now. 18. Traversals: DFS, BFS: Hello guys. In this second lecture, we will talk about tree traversals, more specifically, binary tree traversals. As you already saw. Unlike linear data structures that are arrays, linked lists, queues, stacks, etc, which have only one logical way to traverse them. Trees can be traversed in different ways. Following are the generally used for traversing the trees. We will talk about depth first traversal, this lecture, which are in order, meaning first we go to the left, note, then the root, and then to the right node. Pre-order, which is we first visit the root, then the left child and right child. Let's say we have postorder, meaning we first go left, then go right, and then lastly we go to the root. There are also ESA, breadth-first traversal or level order traversal, which basically takes, prints the note in order of their levels, of their layers. The in-order traversal algorithm would be to traverse the left subtree first, then call in order for the left sub tree. Then visit the root tendon, traverse the right subtree, and then call in order for the right sub tree. In order one, again was first we visit the left child and right child. Uses of in-order. In case of binary search trees. In order traversal gives nodes in non-decreasing order. To get nodes of a binary search tree non-increasing quarter of variation of inorder traversal. Inorder traversal easily can be used. The preorder traversal is pretty similar to the in-order one except the way we do things. So first we would visit the root end towards the left sub tree and called preorder of the lips. Leslie, we will traverse the right subtree. Preorder. Postorder traversal would be first traversing the left subtree, call postorder of left sub tree, then reverse the right sub tree and call postorder of it. And thus, we would visit the root. You see some preorder traversal would be to create a copy of the tree. It is also used to get prefix expression on an expression tree. Post-order traversal would be used to delete a tree, would be also used to get the postfix expression of an expression treatment. If we were now to look at the code that would do these depth-first traversal. First thing, the main function, we will declare the root, note this down using a struct that's called node, and we declared it upward. We have an integrated host the data and then two pointers to the type note that's left and right children. And also a constructor that takes an integral test data, then initializes the children of these nodes to know. So we'd say leaked or not definitely, but just to note it, no children. First we declare a root and then we give it left. And you know, if two bitrate note of three, these are just failures, meaning no two failures. And then left, left we have a node with the value fluorine though they've tried to be a noted the value of five. This right here is how our tree would look. And then we call pre-order, in-order and post-order of these functions takes one argument, that's the root node, for example, with the post-order. Notice don't know, obviously, we will recursively call for the left children, then for the right children, and then we would print the data. So what this would do is it will recursively called left until it arrives to the leaf. Then it will return from recursion and takes him right. Then finally some root value. Then you also have in-order, pre-order already set. Just the difference, only a difference in succession of these instructions exists. In order. Again, check if the node is not null because if it means you're already finished the tree or there is no children there. We then call recursively the function for the left node. Then we will print and then we will recursively call for the right. The pre-order. Obviously. We check again, need to know these nano. First we print, then call recursively far left. And then for talking about the complexity of these algorithms, well, come to the stage. For all the problems are actually server-side pleasing volt because basically iterate. Note. And the auxiliary space, if you don't consider the size of a state for function calls, then it's constant, we go one. Otherwise it would be linear big O of n. Now let's talk about level alter binary tree traversal, which is breadth-first traversal. So there are different methods. We will talk about the method that uses a function to print a given level. Again, largely tried to do here is print the number of nodes in the level order from left to right on levels. For example, for the last tree that we saw, the level order traversal for it would be 12345. The algorithm here would be to implement two functions. One is to print all nodes at a given level, so we give them an apple. The other function is to print level order traversal of the tree. Level order makes you the print keep on levels to print notes at all levels one-by-one starting from the root, we would do is first print level order of three. Go from one height of the tree and print that level. Iterate through all the levels and call print given level. Let you take two arguments, the tree and that level, and print it. The print function, print given level. We check if the tree is known, then it would return. If the level would be one, then it would bring to the world. And it would recursively call been given level of the right and left tree with level minus one. As you can see right here, we made the function to create a new node function that would return the height of the tree. The two functions that we talked about. As I said, the print level order function takes the argument, the root. Then we'll calculate with the height method the height of the tree. Iterate throughout the height and coping given level of root I, which is the number of the level we are on currently. And pink given level is a function that takes the level and note checks if the root is null. If it is, then it will return. If the level is one, it will print the root node. Because if we are on the first level, it means we are at the roots, we would just print it out recursively calling anything. But if we are on a lower level, I'm not the root level, but downloads, we will recursively call this function for the left and right. Note with the level minus one. Hence the second parameter. So I think that's pretty straightforward. Again, you can see for the tree that we showed on the screen, the level order traversal is 12345 is we already figured out. Again here. Complexity for this algorithm is linear. Here regards to the time complexity big O of n, as we iterate through all the nodes once recursively, DC is pretty much the ways you can traverse binary search tree. And they are very useful to know because they will give you more morbidity in a tree. And they will make sure on your sales when dealing with three question on a coding interview. So now let's move on to the next vector. 19. Check for children sum property: Hello guys and welcome back to this course. In this lecture, we will talk about the three problem that sometimes can appear in an interview question. That is to check for children some property in binary tree. What that means is that given a binary tree, you should write a function that returns true if the tree satisfies the property that for every node, data value must be equal to sum of theta will use in left and right children. Consider data value is 0. For now children. For example. If we would have a tree that would have the root, then the left children would be eight and the right children would be two. That would be a valid tree. And so on below, if that child with need to have two children, so left hand try at least that their data in some should equal eight, and so on for the entire tree. The algorithm that we are, we'll approach here is to traverse the given binary tree. And for each node, we should check recursively if the node then both these children said is by the children some property. If so then true else return false. That is pretty straightforward. Let's not jump into the code and see how can we do that on a more specific technical level. All right, here we already declared some stuff that would help us with the implementation of the tree. So we declared a structure that's node. And then we declared an entire tree is some property of root two. Then we will print that the condition is satisfied, otherwise false. So we basically we are going to implement a function that's called East some properties. It takes the parameter the root node and returns an integer, which might as well have been a Boolean, is the same thing because if you either return 0 or one, then jumping into this function, we declare two variables auxiliary that will help us remember the right and left values of the children of the node that we are at the present with the iteration. Then if the node that we are honest or its children or no, then we will return one. Because that means we've reached the end and it's okay because everything checked out to be true up to that point. Otherwise, you will also see that the majority of these algorithms start with the base case of this tree algorithms. First, our recursive and second, start with the base case, meaning the ending case. Well, we have multiple scenarios here. If the left node is not null, then the data in it, so the number that it holds will be given to the left beta integral that we declared here. Then again for the right node, we will do the same thing. And then we will check if the node data, so the number that the node we are right now with the iteration is equal to the sum of the left and right children. And also recursively called the same function for the left node and the right node. We will recursively check the same thing for both of the children of the node. Then we are going to return one, meaning it's true. And our three 0s, with this condition that we are checking, else we will return 0. So what this does is recursively call by using the cost stack. And when it will return from the call stack, it will hit this one. If all the ECM properties will return true, as you can see right here with the end statements, all of them needs to be true in order for this if statement to check out and return one. This is how we will check this condition in all of the tree with a recursive function. Now talking about the complexity of this algorithm, as you are going to see in almost all the tree algorithms. Linear from the time point of view and constant from this base point of view ways we only declared two integrals. But from the point of view, iterate through the entire tree. So that's linear big O of n. Thank you guys for sticking to the end with me on this tutorial and I will see you in the next one. 20. Sum of all the nodes: Hello guys and welcome back to this course. In this lecture, we will talk about another tree problem. Let's give them sometimes in calculating the sum of all nodes in a binary tree. I think the title is pretty self-explanatory. What you would need to do when given this problem is to provide an algorithm for finding the sum of all elements in binary tree. Basically, you need to summarize all the integrals that are held by all the nodes in a binary tree that's given to you. As usual, we will approach this algorithm with recursion as we usually do in three problems. Let's look at the code to see how we would do this problem. We declared a struct. Note that keeps him inductor is the key and also the node's left and right that are kept. By giving them a pointer to the node structure. We drew a tree right here. And then we declared by some integral and we assigned it our function call that's supposed to return the integral. That integral being the sum of all the nodes in the given tree, T only parameter that this function takes is the root node of our tree. Pointer to the node. Obviously. It goes like if root is null, then we should return 0. As usual in three recursion algorithms and methods, we start with the base case, meaning what happens when the bottom call these heat? When root is no, we reached the end. So there's no note anymore because we recursively call this function until we run out of nodes. If that's not the case. So if we didn't reach a route, we should return the root key, meaning the value that the root is keeping inside the because you can see the structure, the key is the integrated that node holds. We also add the recursive course of this function for the left and right child of the root, meaning the note that we are on it. The current call, of course, recursive the dish will be called for the left children. And then again, the execution was started with no return. 0 IS return its value and then again recursively call for each of them. I think you understood how this goes. Now we're talking about complexity of this grabbed row. Well, the time complexity is linear as we iterate through the whole tree is pretty intuitive that we need to iterate through each node so we can find out what value it holds true to ourselves. And then the space complexity is constant as we do not declare any elements other than the standards of Carsten sold yet it's big O of one. Thanks guys, and we will see each other in the next lecture. 21. Check if all the leaves nodes are at the same level: Hello guys and welcome back to this course. In this lecture, we will talk about yet another three problems that might be given into an interview environment. That is to check if all the leaves are at the same level in a tree. In this problem, we'll ask you to do is given a binary tree, you just need to check if all the leaves nodes, meaning the nodes that don't have any children. So the ones that are at the bottom level, at the same level or not, basically imagine the root being on level one, immediate children being on level two, and so on. Until you find the leaf level, it has usual, we will approach this algorithm using recursion. Now, the idea is to first find level of the leftmost leaf and store it in a variable. And we will use that variable. Then compare level of all other leaves with debt level. If it's the same, we will return to end otherwise false. We traverse the given binary tree in a preorder fashion. The level that we keep in mind, we'll be best to all the calls as an argument. The value of this argument is initialized with 0 in another function to indicate that, firstly, if he's not yet seen, the value is at the plane. First find a leaf or level of subsequent leaves in pre-order is compared to this level argument. Now let's take a look at the code. We declared the node structure and the constructor for it. And in the main function, constructed three for us. And then we have a function that's called check that takes the root of our tree. And what it does is that it initializes level in leaf with 0 and returns the code to this check, a function that takes as parameters the root of our tree, then the level and leaf level that are both initialized with 0. As you can see in this check until function. The base case is when we have a root, that's now. And then we should return true. Then the children of the node that we are right now are both null. It means that we arrived at a leaf node. And then we check if it's the first time when we arrive at the leaf node. How we do that is by checking if leaf level is 0, as you can see here, he's passed by reference, so the value of it remains. The one when we call the leaf level is 0. It means that it's the first time when we encounter a leaf, we assign to this leaf level, the level that we are at right now. Furthermore, if we don't enter this if statement, we then return level equals to leaf level. What this means is that we are right at leaf. What is now the Firstly, if we are right that we should return whether the level is equal to the leaf level. The leaf level is the actual level of the first leaf we arrived at. All our leaves needs to be at the same level. That's why we keep in mind this variable right here. Then exiting this if statement, meaning if it's not a leaf that we are at, right now, we return recursive calls of this function for the left and right node. Because we are right now at the node that's not a leaf and Xist, which means we are at a parent node. We need to recursively call this function for both of these children and increments the level. Also, while keeping in mind the leaf level, it's the bottom most level of the first leaf we ever encountered. As I've already said, I will stress this. Again. We remember this leaf level debt, the level of the first leaf that we have encountered. And this is the reference that we will check. Furthermore inode next leaves that we will encounter for the complexity of this algorithm. Again, the space complexity is constant. This we do not use any additional space bigger of one. And then the time complexity is linear. As we traverse the entire tree to find firstly, the level of the first leaf and then checking all the other leaves to have the same level at the first leaf that we encounter. Thank you guys for watching this tutorial and I will see you in the next section. 22. The balanced brackets problem: Hello guys and welcome back to this course. In this lecture, we will talk about the problem that's very often given in an interview question. That is to check for balanced brackets in an expression using a stack. Well, that's done using a stack, but the interviewer might actually not deal. You get this problem done using this taken tonight, figured that out for yourself. The problem gives you a string. That's an expression, and you need to write a program to examine whether the pairs and the orders of the brackets, correct in that expression, the parentheses can be currently normal or squared. For example, I will put on the screen right now two different inputs. So you can see that the first one is balanced and the second one isn't. You cannot close the square bracket before closing the normal one because there is not the natural order. What the algorithm would be to declare us deck that holds characters and then traverse the expression that you are given this string, basically iterate through it. In dendrite two scenarios. First one, if the current character that you are iterating through at that moment is starting bracket, Start normal bracket, starting curly bracket or starting squared bracket, then you can push it to this deck. The second scenario is if the current bracket that you are currently on right now with iteration is a closing bracket. Again, a closing normal brackets, closing square bracket, closing curly bracket. Then pop from this deck. Right now you are pumping the top element and you are going to see what is the last open bracket. And if the pop character, so the last open bracket is the matching starting bracket, then it's okay. The brackets are not balanced. So after complete traversal, if there is some starting bracket letting this deck, then it's not balanced because in our string there exists opened brackets that I have not been close to the end of the expression. Let's look at the codes right quick. We have a main function and read exert an expression that goes like starting curly brace, starting curly brace, starting normal brace, ending normal brace and the curly brace. So that is okay. Then starting squared bracket, ending squared bracket. This should be a balanced expression because there are not any brackets that are left and opened or closed in the wrong order. Now we have a function called, we declare the function that's called our brackets balanced that we are going to see it has one parameter, that string. We declare a stack, as we already explained why that holds the type of data char. Then we declare an auxiliary chart called X. For int i from 0 to the length of the expression. We iterate basically with this loop through each character of the expression that is given. We take each character one by one and verify what type of bracket these. First, we need to see if that bracket is currently squared, are normal and it is starting in type one. If it is, then we can push it in our stack and then we continue as we don't need to go forward with the rest of the loop execution. Otherwise, if it's not starting bracket, we can check if the stack is empty. And if the stack is empty, we should return false. Because it means that is a closing bracket. Is it cannot be starting bracket because if it would have been, the execution wouldn't be right here, right now. It's a closing bracket and the stack is empty. What does that mean? That means we have arrived to a closing bracket that has no matching starting bracket before it. So it's not a valid expression of parentheses. If that's not the case, we have a switch statement based on the character that we are right now in our expression. So we have different cases. The case when our character is a closing normal bracket, we are going to. In our auxiliary character x, the top of the stack. And then we will pop the top of the stack as we don't need it anymore. And then we are going to verify the value that was in it. If the value that was seen, it was a starting curly bracket or a starting squared bracket. Then we should return false as we arrived to an ending normal bracket and list one that was open, so it's matching bracket was not the same type that EDs. And then we should break. In the other cases, if it is a curly bracket that is ending, and then the starting matching bracket is OK. The other two types, It's not okay, so we should return false. Then again, if it's an ending squared bracket and its matching parenthesis is normal or a curly one. Again, it's not a valid expression, so we should return false and then break. The same procedure also applies, where we put in our auxiliary character the top of the stack, and then we pop it. When we are done with the iteration that our stack should be empty. So there should not be any parenthesis left opened, because that means they don't have any ending parenthesis that are matching. If the stack is emptied means that all the markets have matched. And the expression is valid. If the string is not empty at the end of the execution, that means that there are some elements in it. And as you already saw, we only push in it starting types of brackets. And that means that in it are left starting brackets that have no matching ending brackets. And that means that's not a valid expression. So this function is called in an if statement. So if this function right here, meaning this function is returning true, we can return that the expression that we are given is a balanced expression. Else it's not balanced. So as you can see, knowledge sample, if we run the code, you can see that it says balanced, so it's balanced expression. Now let's talk about complexity of this algorithm. The complexity of this algorithm from a time point of view, this linear as we iterate through our expression one time. So that's big O of n. Now the space complexity is also linear as we declared a stack that can hold as much as the whole string. In the worst-case scenario where the string contains on starting brackets. You can do this in a more efficient way where you don't even remember this deck. And instead of this deck, you can remember some numbers. For example, some variables that you increment when you meet a starting bracket and decrement when you meet an ending bracket. That's a more advanced solution. It you might try at home or search for it. But the basic solution for these problems, this one and this one you should really understand and know by heart. But thank you for sticking with this tutorial to the end. See you next time.