Engineering Interview: Improve Problem-Solving in Python! (Coding Interview) | Lukas Vyhnalek | Skillshare

Playback Speed

  • 0.5x
  • 1x (Normal)
  • 1.25x
  • 1.5x
  • 2x

Engineering Interview: Improve Problem-Solving in Python! (Coding Interview)

teacher avatar Lukas Vyhnalek, Microsoft Employee, Programming Teacher

Watch this class and thousands more

Get unlimited access to every class
Taught by industry leaders & working professionals
Topics include illustration, design, photography, and more

Watch this class and thousands more

Get unlimited access to every class
Taught by industry leaders & working professionals
Topics include illustration, design, photography, and more

Lessons in This Class

19 Lessons (3h 2m)
    • 1. Introduction

    • 2. 01 Palindrome

    • 3. 02 Delete duplictes

    • 4. 03 Counting characters

    • 5. 04 Check if is subset

    • 6. 05 Random Print

    • 7. 06 Functions in Python

    • 8. 07 Reverse Matrix

    • 9. 08 Sublist with given sum

    • 10. 09 Missing number in array

    • 11. 10 Pranthesis Checker

    • 12. 11 Stock Buy and Sell

    • 13. 12 Number of leaves in a tree

    • 14. 12 Number of leaves in a tree (using loop)

    • 15. 13 height of a tree

    • 16. 14 are trees identical

    • 17. 15 Sum up numbers in a string

    • 18. 16 Wave from array

    • 19. 17 The Max sub array

  • --
  • Beginner level
  • Intermediate level
  • Advanced level
  • All levels
  • Beg/Int level
  • Int/Adv level

Community Generated

The level is determined by a majority opinion of students who have reviewed this class. The teacher's recommendation is shown until at least 5 student responses are collected.





About This Class

Are you someone who wants to improve problem-solving skills or prepare for an upcoming software engineering interview? Then you have come to the right place!

In this course, you will improve your problem solving skills and prepare for an engineering interview with 18 real-world coding interview problems. Solving those problems will improve your problem solving capabilities and help you get a software engineering job.

Hello, my name is luke and I will be your instructor throughout this course.

In this course, you will prepare for your coding interview in python.

Basically I will show you how to solve real-world problems. That often comes up at a software engineering interview

These are the type of problems you can get at an interview in one of the big tech companies like Microsoft, Amazon, Apple, Facebook, and Google.

If you practice your problem-solving skills on these problems I promise you, you will be

better prepared for your interview.

So who is this course for?

  • This course is for a person who is preparing for a coding interview

  • Also, it is a good match for people who wants to get a job at one of the big tech companies and they need to pass the coding interview before they can get to the in-place interview.

  • And overall if you just want to improve your problem-solving skills, this course is made for you.

Another thing I want to mention is that this course is not designed for absolute beginners. It requires that you know basic programming concepts such as function, variables, if statements, loops and so on.

Also In the course, I am using some data structures to solve some problems so it would be great if you would know what I am talking about. I use only basic data structures like Binary search tree or Hash table.

In the course, there are currently 18 exercises on which you can practice your problem-solving skills.

You have the source code that is written in python available to every exercise.

And if you get stuck or if you don't understand something you can always reach out to me. Mostly I respond within a day.

So do you want to improve your problem solving skills?

Enroll today and I will see you in the course!

Meet Your Teacher

Teacher Profile Image

Lukas Vyhnalek

Microsoft Employee, Programming Teacher


Class Ratings

Expectations Met?
  • Exceeded!
  • Yes
  • Somewhat
  • Not really
Reviews Archive

In October 2018, we updated our review system to improve the way we collect feedback. Below are the reviews written before that update.

Why Join Skillshare?

Take award-winning Skillshare Original Classes

Each class has short lessons, hands-on projects

Your membership supports Skillshare teachers

Learn From Anywhere

Take classes on the go with the Skillshare app. Stream or download to watch on the plane, the subway, or wherever you learn best.


1. Introduction: Hello. My name is Luke and I will be your instructor throughout this course and this course, you will learn how to prepare for your coding interview and fightin. Basically, I will show you how to solve real world problems that are often asked at a software engineering interview. These are the type of problems dead you can see at a interview at one of depicted companies like Microsoft, Facebook, Google, Apple, Amazon and others. In my opinion, the overall goal off this off this course is to actually improve your problem solving skills, which can be used then on like you're even on your project. Not necessarily only at the interviews, right? So this is a skill that is nice to have for life, not only for interview. So the overall goal is to improve your problem solving skills by practicing how to solve those scolding interview questions. So who is this course for discourse is for anyone who is preparing for a coding interview. Add one of the big tech. So if you want to get a job at those big tech firms like Facebook and so on, um, I I think that it is absolutely necessary for you to actually practice your problem solving skills. So he has Mostly. This course is designed for a people who want to improve their problem solving skills and then use their problem solving skills at the actual coding interview. Another thing that I want to mention is that discourse is not designed for the complete beginners, right? If you are someone who is just starting with programming and you don't know like those those basic programming concepts like loops, functions and conditions, this course is probably not for you. Also use some basic data structures, like stables and binary tree to actually solve some of the problems. And also, some of the problems are defined on those data structures for example, county number of leaves in binary search tree and stuff like that. So it is quite necessary for you to actually know how these data structures work and how they look like in the course. There are currently 18 exercises on which you can practice your problem solving skills to every each. Never exercise. There is the source code written in python available so you can just check the source code . But it looks similar to yours may be done a g o check D solution that I have. I talk through dissolution. In those video lectures, I describe everything from the time complexity and I also along the way when I can solve the problem, I try to give give you some tips about how to actually approach the problem about things that you want to ask your interviewer. Yes, so kind of best practices if you want. Yeah, and another thing that I want to mention is that my job does not end by making these video lectures. If you have any problem, if you get stuck or if we don't understand something, you can always reach out to me. Mostly I respond within a day, and yet, so that's pretty much it. Thanks for a time, and I'll see you in the course. 2. 01 Palindrome: Okay, guys, welcome to this lecture and this lecture. We will talk about whether a string is a palindrome or no. So what is actually a palindrome? Well, burning drum is a string, uh, that basically, if you reverse the string, it is equal to itself, right? It is still the same strength. So, for example, an ABC is not a palindrome because if you reverse it, you would get C B A and does to are not equal, right? And if I, for example, put another example here and let's write, for example, a b a and then I reverse it to once again a be a right. This a is the is the 1st 1 in this case, but does strings are the same? So this is a palindrome and yes, so let's actually write a code. And, Dad, you can figure out whether a string is a pound drop so will define a new function, for example, s ban drum like this and it will accept the string, right? And what what it will do Well, in order to figure it out, we can simply just If you want to write us on one line, we can just return whether the string is equal duties drink in the reverse because faith and already have the function that case returns. Sorry about it. And because beytin already have a function dead basically can reverse the string. So you don't necessarily have to write the code yourself. So if I actually bring this out So if I put in here print and let's actually to sit out so print and in here less right, it's bound drum. And then inside here, we can put, for example, those two strings. So ABC, the 1st 1 should print false, and the 2nd 1 should bring true, So a b A, for example, And let's actually run this. So if I run the file, I think that we should be correct. Okay, We got a problem and string have no attributes. Reverse. Okay, So how do we How can we actually g o around it? Well, if string have no attribute Reverse, We can basically reverse it like this. Okay, this will reverse this strength, and currently it is actually working. So basically, the point is that in here you want to reverse the strength and if you, for example, don't notice you can actually write a method for it. So, for example, death or reverse strength. And inside here we will accept some sort of strength, and what we want to do is actually reverse it. So as I said, there are a number of ways. But if we just want to create the, um, sort of, like new string and returned a new string, we can simply do that by just creating, for example, new string called result. And, uh then for every character in de string, we can just append upended character to the end of the string, right? So results will be plus will be equal to result blasts see. Okay. And now, if I return the result ah, the result will be the reversed strength. Okay, So if that's not clear to you, I e I can go for the coat. So inside, he redefining new string, and then we go from left to right in the in the original string. Okay, So from left to ride and we a pent each of the character to the end. Right? So we take the 1st 1 and put it at the end. Then we take the 2nd 1 and we Okay, so that's actually not correct, right? We need to put it in front of it. So inside here, Right. I actually figure out that I get a mistake here. Okay, So it should basically be in front off the thing that we already have, right? You may have wondered about it. And if you did see something wrong about this this line, you were correct. So these the character that we are taking next should be actually in front, off all of those that we previously take right? It makes sense. And eventually, if we go through all of those characters, we can just return to string. So inside here, we can just remove this and type in here, do you river strength and passing there d strength. And it should bring down the same results if I'm not mistaken. So it's actually run this again. And as you can see, there are the same results 3. 02 Delete duplictes: All right, so ends lecture. We will actually go through the problem off the leading duplicates from an, um, Ray. Okay, so but zoo did. So let's assume that we actually have a input off. For example, some list off in teachers. OK, so let's say just one to go on for 566 And we want to just remove the duplicates. So from does the output of our algorithm, as should actually be one, too. Then the one will be removed and we will get 45 and six, Okay. And yes. Oh, I think it's pretty clear what we should do. Right. So let me actually go through the code. So if I just defined the remove duplicates function, and, uh, and it will basically take the list, so just type our for it. You can maybe just put in here some different name. That's up to you and Ah, yes. So what do you actually want to do is, for example, one solution. The simplest one I I recommend when you are at the interview, you start with the simplest solution that actually works. And then you work your way up to a better solution. So for example, the simplest could be just if I just create a new result array and then for each in teacher . So for each value in D. L So basically, in the input on, I will basically check if the value is in, Uh, do you result? And if it iss, I will do nothing. But if it is not so, I would not in here, I will actually added to it. So result dot upend and evil, right? And then I can just remove It s a really return it as the return result, right? So if I just just it out So, uh, brand remove duplicates, and I will just take this input and we will check. So remove duplicates from this list. And if I run this inn in terminal, it should basically give us this output and a dust. Okay, so it actually works just fine. Um, right now, when you basically present this solution, the interviewer may actually ask you about D time complexity off this solution so you can either balls the video and think about it for a second. Um, if you know what time complexity means, it's basically how fast the algorithm is running, and it's usually a myth Matic function. And yes, so, for this algorithm, um, what we are actually doing well, we go for every element in the list. Right? So this is basically end times, right? If n is the amount off off off elements in the list, right, we will basically do whatever is inside the loop end times, right? I think that makes sense. We just give forever element, and each element is just one. So in times, um, and what is happening inside here? Well, inside we are actually checking, um, for a whether a value is actually in the result. And, um, what we are actually doing, It's basically if you think about it in the first situation. Ah, we just need, like, one check, right? Any second, there s probably already one element. And yet in the worst case, you always need to Sorry. You always need to think about the worst case scenario. And the worst case scenario is that the input will be something like this, right? So the worst case is that the input is something like this. So basically a array off integers but that the array have no duplicates. Why? Um, because then in the result, and in this check, we action need to go through all of those elements. Right? So we need to go for one element. Because if you think about it, we in this loop Val is equal to one. It is not in result. And we were added to the result. Right? Then in the second duration, we already need to check another number. So there will be to write once again, we will add it. So the result, basically the size of a result, is actually growing. And with when we with each and every other element, the result ISS still growing right. And we need to check for more numbers, actually, in the results, right? So then there's, like, free numbers. Then there's four right and so on and so on until, like, n minus one. And then we add basically the last ah, the last value, right? I think that should make sense. So what is actually the time complexity? Well, in the worst case, we get something like n times and minus one. Sorry. Um, yeah. If if you are aware off the mathematics and how this works, we basically go to end times all of this, right? Ah. Which basically gives us n times and minds one and all of this divided by two. All right, if I'm not mistaken. Um, okay, so there should be, like, divide. And this basically results in a Oh, big o off and spared. So this is not that great, right? This is not a great time. Complexity and some. So how can we actually improved this algorithm so that it runs faster? Um, so in this particular case, do we have to go through all of those values? Well, yeah. I mean, how else are you going to check? Right. You need to go through all of those valleys and some bad. What about this one? Is there some better way to actually store the result? And, um, so that we don't necessarily have to check all of those numbers in the result? Let me think about it. Do you know data structures? If you know, data structures, you could use something like a balance tree. So, um, balanced tree, right? As a result. And if you know, for example, like red, black tree or air trees, Right. Um you know dat dose trees have basically look off an, um, times for search, right? If you want to find out whether element is in the tree, it's in the worst case. It's luck off. And so if we used some sort of balanced tree, um, you could also use, like, BST bar with BST beina research tree. Um, you would you wouldn't actually be sure whether the, um, time complexity gets better, right? Because in the average case, it's Logan. But in the worst case, it would be ah, and still end right. For example, if we would insert all of those values, it would still be an time complexity, so we wouldn't help each other. But if we use some sort of balance tree like red, black tree or something like that ah, we actually get instead of and squared, we would give you get ah, basically end times Lagoven, uh, which is much better than and squared, right. If we would have, like, a huge array, Um, this is much better. This is much better. And yes, so can be improved us even more. Um, do you know any data structure that can search? Ah, with better time complexity then look, Anna. Yeah, yeah, if you already know it, it's the of course it is the hash table, right where you're basically hash out d element and figure out whether it is actually stored in the You're a right. And the hash function is actually constant. With the hash function, you can have collisions, but those collisions doesn't, um, happened debt often, and yeah, also in the interviews, you also need to be quite aware off function doesn't necessarily have ah, constant time, right? A lot of times in school, they teach you that his function is just constant time. It basically takes an element and return some. Indeed, you're right. Some index where you should store it, but it actually doesn't work in constant time for some complex objects. Like like, for example, like string. If you have a long string or if you have, like, huge numbers, right? Even, um, it doesn't actually work at a constant time. And that's something that the interviewers will basically notice. Right? If you if you tell them that it doesn't necessarily have to be in constant time, they will basically say that you are great. Um, yes. So didn't there is definitely definitely one thing to keep in mind. Ah, yeah, but actually back to our solution. So how could you actually go through this and figure out? Um, basically what? How to actually improve this where d hash function on and where? Like, Yeah, I d hash table. So in python, you have actually a data structure called dictionary, which is basically a fish a hash table. Right. And what you can do is just used the dictionary in order to solve this problem. Another thing that do you may want as the interview is, for example, how how long or what is the range of these numbers? Um, another thing that you may want to do. And it might be even better if the range of those numbers is some somehow small, for example, like those numbers can be from 0 to 1000. You can just create a array off 1000 elements and then basically in here, just check Ah, whether it is equal to, like, initialize it. Zero and inside here, check 40 index. Right. And inside here said the index to one and inside here. Just check if it is zero, and that's how you can do it in constant time, but let's just assume that those numbers will be huge, right? And we want to have them. So and also it is better if, for example, dis changes to strength or something like that because his function works for anything. Basically, Um, yes. So we can just use those dictionaries and, um, what we can actually do is just inside here. Said this, for example, to know, like, one it very much Doesn't matter what you said it too. And, uh, then Wiggins returned. Ah, kee's right inside here. So if I go through this once again Ah, yeah, basically returns the keys. You can just convert it to list if you want it very much. Doesn't matter, and and it should have the exact same results, right? So 12456 But in this case, we are getting it and basically and times, um, kind of constant. And but this is like without collisions, right? So if you don't count collision. But if you count collisions, um, you can actually get a worse time. For example, something like Well, in the worst case, you will actually get a depends on how you actually how this is actually solved inside. Right? But in the worst case, you can technically get a ah, basically end so n times and you would still have own off and squared. Um, but it is extremely, extremely unlikely. And especially if you have, like, big big dictionary, it's like, extremely unlikely. And this is actually the best solution that I can offer. If you want to shoot for the best time complexity in the average case, you can get it. Body has table, OK, And this would be end times basically one So old fen, which is great. And then if you want to shoot 40 worst best off the worst case time complexity. You can actually use some sort of balance tree and you will get n times. Look in, OK, And if you tell this to your to your interviewer, I promise you that he will be He will be so happy. Okay. So Dennis, for much it for his lecture I hope you enjoyed it 4. 03 Counting characters: All right. So let me actually go through a not algorithm that we can solve. So in this lecture, we will basically count the number of characters that appear in the strings. So, for example, if we have, like, some sort of this string again, see that A Is there, like, two times B? Is there free times, right? And then s Is there, like, one time and the is there two times, right? This would be our output, right? This is our input. And yes, so that is actually what we want to do. Um, so let me actually define a function that does this. So inside here, we can just defined the for example, account characters like this, and it will take the string. And what we will actually do is just create a new dictionary, right? That's the way to count characters. Why? Well, because we can just save d character as a key. And, Dan, um, Dean, we can just update the number of characters. Right? So all we have to do now is just go for every character in the string and basically check if the character is in result. Ah, what we can do is just update the result on the index of the character, right? And we just want to add their one and yeah, and else we basically want to initialize it. So result on D. C. Ah will be equal to one, right, And also add the current character, and then we can just return to you result, or if you want to also print it, we can just now go for, um every key and value in the result Ah, items and just printed out. So, friend key about you Simple is dead, and I can just come and this one out and let me actually call it So county characters and for example, this one and let's there like this and let me actually run this file. And if I run this, I'm not sure. Ready? You can see it. But A is to B is free. S s one n ds two. So it actually works just fine. And bar. As I said before, you should start with the simplest solution and then improve from that on birds. And do you think that there is a better solution for this? Um well, yeah, I think that we are doing actually quite a good job. Um, we are actually adding, using the character as a index for this de hashing Gissin constants time usually and actually for for one character, it it is in constant time. And, um yeah, and yeah, and if there are little or no collisions Ah, we actually get, like, basically this will be just over a friend, right? D time. Complexity off. This is open, which is great, and yeah, but maybe we can improve the readability off this. So let's actually improve it. Why? Using the default dictionary. So, first of all, we need to import it. So from collection, uh, import. Oh, import. Ah, the default dictionary Like this. And inside here, we want to actually change it to default dictionary. And what it basically allows you to do is just create a dictionary that already have a pre assigned value on in this case, we use and and dentist zero. Okay. And, um so all we have to do now is just remove those lines and ah, and also the els because we don't necessarily have to check whether it actually is in the dictionary, because if it already is in the dictionary. Um, we basically we basically just update it. And if it is not in the dictionary, we won't get an error because it is set as a default off zero. So if I run this file once again, we get the actual same result, but instead, off having it like six lines. Um, yeah, we are. We only have, like, few lines, right? And there. But if they say that you, for example, cannot use the default dictionary which is said about yell, it's assumed that you cannot use it. Ah, you can Maybe just said this to basically result that get and inside here can said the sea . But you can also define the default daddy. Right? So what that actually means? Let me just go through this family quickly because I know that some of you already know what I'm actually doing. Um, yes. So you are actually setting the sea to the result off getting the whatever is on the character see and get method for the dictionaries is quite straightforward. If the key So basically, in this case, the see the character eyes in the dictionary, it returns the value that is associated with dusky right? Eso It's actually the same as asking. Distinct. Okay, but if it is not, Indeed dictionary Ed will return this default value that you actually pass in here. So if we are adding the character for the first time, we were basically said it to syringes shouldn't be here, so we will set it right? We will not add it. We will set it to whatever we get. In this case, we will get zero because it is not in the result. And then we will add one. So we will set it to one. And if I run this style, we will get the same results as before. About this time, we are not using any libraries. We are just using the built in get method. And I actually think that this is the best solution for this problem. And yeah, and that is for much afford his lecture. I hope you enjoyed it. 5. 04 Check if is subset: Hello, guys. Welcome to this lecture and this lecture. We will actually talk about the checks. Upset problem. So what it actually means well, imagine, Dad in the input. We have two lists, OK? And we want to check whether the first list this subset off the 2nd 1 So, for example, we have, like, round two for and seven and, for example, a whatever. And we want to check whether it is a subset off this be, um be a and then 12 free for ah, seven hand. I think that this should be true, right? Because if this element is in there, right, this element isn't there. These lemon isn't there, this one also, And this one also So this should result into true right? And so yeah, let me actually define the function. Let's just call it this upset and we will accept the list. One and us too. And we want to check this. So what is the simplest way to actually do it? So once again, start with the simplest way. So, for every element in delist Juan ah, you can just go ahead and check if it iss so if the element is in, ah, delis to And if it is, if it is, we just want to move onto the next one. But if it is not so if it is not in delis to Ah, we just want to return false, right, Because we okay, because we already know that if one element is not in the second list, we already know that it doesn't. We don't have to check all of the other elements, because, yeah, it's not already a subset. Because in order to be a subset, it needs to the second list need to contain all of the elements from the 1st 1 And if we just end up the loop, we can just return True. And yes, so this is the simplest way to do it. So if I just bring to do result off its upset overdose to So for example, this too on just based it and put like this and let me actually run this file, and as you can see, it's is true. Right? Um, why does show this is true? Well, as I said, it actually works. And, um, yeah, Okay, So how can you actually improve it? Or let's say, let's start with. What is the time complexity of this ocean? Um, so inside here we have an right. And then inside this loop, we are runs again checking the l to write eso this in the worst case. Once again, we have the line from 12 and minus one, and, um no, actually. Sorry. Sorry. We actually have, um we actually have an And if if we assume that dose shoeless have the same size we basically have, like, and and and so we basically add up all of those end rights. So we basically get end times M plus and plus and plus plan and so on. Um and that basically means that we have the, uh, and square time complexity. Um, yes. So can we improve it once again? Sure thing. Ah. Weekend just can change this. This thing, the l two into a dictionary, right? And, um yes. So this would be a good thing if you can do it on your own. Um, just if you try to do this right, um l two is equal to dictionary from l to you will get an error because the second argument is also required. And if you put for example something in there? Ah, you will get once again an error. So how can you actually go around us? Well, in order to do that, you can just maybe create a new well, let's call attempt. And then we will use the dictionary temp and then just go for every element in D l two and ah, yeah, I was just added, Right. So them on the index off the element will be equal to one. Whatever you can set it to, whatever whatever you want. And right now we will get just e. Uh, we were once again get true bad. Currently, we are doing this in a ah, linear time, right? So often, because there is like, oh, event. And this thing is constant if we don't count the collisions that happen in the table Um, yes. So is there a better way to do it? Um, yeah, there is. There is, like, some sort of face in syntactic sugar if you want. Um, we can just create a ah elements, for example, with e and one. And we can just do it for every e in l two. And this is basically the same thing is writing this loop Onley. Currently it looks a bit better. And if I run this thing and surely it works, right and we get true. For example, if I change this to see, we should get false. So if I run this again, um, we get false. Okay, so yes. So that is actually how you can check whether a one list it's subset off another list? Um, yeah. If you have any questions, feel free to ask them, and I will see you next time. 6. 05 Random Print: All right, so let's get straight into it. We have a random inputs. So, for example, an array. Ah, that half like size off N on. Let's just assume that this will be, for example, 100. Um, okay. And then what do you want to do? Is basically bring tout Renda, m'lee all of those elements, right? But randomly, they they need to be random, and they're so let's actually do it. Um, so the simplest way once again to do it, for example, print random. Um, yeah. We also need to import random. I'll just do it, uh, right away, okay. And eso we need to friend to random in some sort of list. And, um, yeah, um, So the easiest way to do it actually is to just go through the list or sorry. Just generate a random number and print the from in the range of zero to the length off the list, and, um, yeah, and then just print it out. So, yes. So, for example, we can just do it for E and the range off zero and then deland off the l. Right. And we want this to actually, Yeah, let me actually start, Add the length So we will start a D and and it will go to and minus one and minus two and all the way up to zero. Right. So the jump will be minus one. Okay. And so each iteration it go decrease by one. And then what we want to do is just, ah, basically compute the index to delete. Okay? And this will be just random around end and between in the range of zero to I and then we can just delete, um, the lead it from the list. Right. So if you are a if, you know, Python, you know that you can just delete, uh, with like this, right? And it is internally somehow implemented. So dead, it is definitely time efficient to do this. And before we deleted, we actually need to print it. Right? Um, like this eso if I, for example, call this right now, it should actually work, right? Because we delayed it, and then we move on. And when we deleted the size the length of the Ellis, actually, it actually decreases. But we also decreased the wise so it should work. Um, if I just called us d print print random with, um I know. Let's say just that. We just have, like, 12 free four five I can write. Um, yeah, we can, Maybe at some sort of letters to it, so that it is more interesting. I could have also used a the D range function to generate this. I'm not sure Why did this? Um yeah, us. Okay, so we get the index out of range. Um, yes. So obviously we want to start at lane minus one right on and like this, and right now it actually works. Um, then it brings none true. Why? So if we get one, um, yeah. Okay. So I don't see Okay. So instead of two, it printed none. Um wow. So we have a back in here, so if I just bring to d um, the next to delete, or like, let me just do it this way. So I'll bring the number on then the index to dilate. So basically, on what index? The number s, um Yeah, we get none. Oh, I'm sorry. I just I just printed here. Okay, So that's Dean on what's happening on defy. Run this again. I'm not sure. Where do we get all of those numbers? Ah, we don't. Seven is missing. Right? Um okay. Okay. So what is happening? Right. I can't do minus one here. I had to do it in here. Um um, okay, if it works correctly, I think that's right. Now I explained this. Okay? It works. So, uh, what mistake did I make? Well, actually, before this minus one was here, it actually generated a number that was outside of the range. Right? So when we asked for the index, we actually got a number that was the same as the length off L Ah. But we index from zero. Right. So the last element ISS at index off length of L minus one. And so debts. Why we have to generate inside here. The Mex number must be the l minus. Wanna write or, in other words, the length off the list? Minus one. Um, yet it's kind of my bed. I thought that the rent and actually generates number that are smaller than this higher bound. Ah, but it is a matter of fact. I didn't know that I'm currently smarter. It also generates the number that is in there? Um, yeah. And this also, if I put minus one in here, it also caused the mistake that we didn't bring, actually, all of those numbers, but we skipped one out. Um, Nandi a But if we just remove it and keep it this way, it actually works just fine. And yes, so what we can actually do now, iss Let's say that the the interviewer is kind of pain and yes, and he wants us to actually not use this delete. Right? So he say just okay, so that that works. But let's just assume that you don't have this delete. Ah, and you cannot use it. So what will he do? So I'll just actually, um, create a new meth new function for this, And I'll just rename this to with the delete and keep it this way. And inside here, we just can't use the delete. So, um, what do we want to do? Well, um, we just want to remove a element that is on this index, right. And, um and we cannot just remove it like simplest. So how do you actually do it? Well, we can just leverage defect the D range, right? the guy is smaller, right? With each iteration, the I get smaller by one. And so what? We can actually do s, um just swap in here, swap the number that is on the index to delayed or just override it. We don't. Well, you will not need it anymore, right? If we don't need this list anymore, we we can just simply override it. Um, with the element deadest on the index. Why, right? Why minus one. Sorry. Ah, yeah. And that will actually delete the element. And then we just generated that we just print it and yeah, it will also take care of the utility. Thanks. So let's do that. So I will just set it to l on the index off I minus one. So basically, I will take the last character and or last element and put it on the somehow randomly generated index. So let's say that we print free. Um Then what will happen is that we will have seven in here and free in here. But we cannot generate free anymore because the y I write, this one will get smaller idiot aeration. So currently we are expecting we are just like assuming that the l is just this size, right? So we kind of trim it right, And and that is why it actually works. So if I just run this again and it should actually work, So if I run it as you can see it, I think it works for one sticks free 752 Yet in my opinion and works and death. So that is basically how you can, um, how we can tell your instructor. Dad, you can actually do this without the delete function. And this I think that this is even more efficient than the delete function. To be honest, I'm not sure how it is implemented inside, but I assume that there is some overhead because they need to move the memory right. They basically in the memory, they just delete the element that it's on the index and just move all of those elements from behind Ah, to the position. Right. So there, that is a lot of work. And if you can do it just this way, it is actually faster. Um, yes. So that is sexually pretty much it for this lecture. If you have any questions, feel free to ask them and I'll see you next time 7. 06 Functions in Python: Okay, guys. So in this lecture, I will go through a bit of a tricky Alana. So let's assume that, um okay, let's assume that we have just some function debt. Okay? I have the capsule. So some function that we can call the the function will be called D. And we can just past there, some render some some input. So, for example, some interior. And then when we call DF function, right, this one, this one, this one will return a function. And then when we call the F function, for example, right now, D um, let's say the 11 will be printed, okay? And then if I call this again, 12 will be printed. So 12 ah will be printed. And yes. So if you are someone who actually doesn't know a lot about by thin and how it actually works Ah, you may be in a bit of a trouble, right? If if he asked you something like this, um, I think that he you will definitely need to think about it. And I'm not sure whether you can came up with the solution for this, but thankfully Ah, I can show you how to actually do it. So if I just defined the d function, it is actually fairly simple. The D function. Just accept the start, right? The start, Paar meter or argument. And then what? It does ISS, for example. We need to also store it right, And then we can just define a inner function, right? So in our and this one will take no arguments. And this one will just All it does is it brings d tent and yeah, also, um, it needs so increased de temp. Right? So I will just adds to distemper one and imprinted. And then all I have to do is return this inner function. If you are someone who is familiar with by thin, you know that this solution doesn't actually work. So if I run this python file ah, we will get an error. Okay, We get an error and that its local variable temp is referenced before assignment. What does that mean? Well, inside here, it just assumes that it just doesn't see this temp variable. It assumes that it is local. So what I can do is stopping here known local and intent. And if I run despite vile again, it actually brings 11 and 12. Same as right here is expected. Right. So, um yeah, that is actually how we can do it. Um, if you, for example, remove this line and inside here, just type start and then inside year ones against start and then start, uh, and run this run this file. Ah, you will see that it actually works to, um And it's up to what solution you want to use. Right now, it actually uses the start from that bus pass to dysfunction. I think that the solution is even better. Um, yes. So this is not necessarily about, like, algorithm kind of question in the interview. This is more of a by thing question about what do you actually know about Bison? And it is definitely a good thing to keep in mind. And in some cases, this is definitely a useful thing that you can can use to solve some sort of problems. Um, yeah, I'm so dead is very much at 8. 07 Reverse Matrix: I guys, let's start read another solution. So Ah, in this lecture, we will actually reverse a matrix. So Ah, what is actually a matrix? Well, in computer science, you can think of a matrix as a Well, In this case, we'll just have a two dimensional matrix, and it will be represented as a as a list of lists. And you can, for example, see this as a as a matrix. So, for example, this one Ah, and then inside here will be, like, free and four, and yeah, if I put this all of this into another list right inside here, we can just get, like, free and six and stuff like that. So, for example, uh, sorry. Five and six, and I'll close it. So this will be our matrix representation. And what do we actually want to do? Well, we want to reverse it. So the outs boot Ah will actually be quite the different one. We want to reverse it with the rose. So, first of all, we need six and five in the beginnings, and then one and two at the end. And then we also want to reverse does Rose. Right? So we want also there to be six and then here to be five. We want free here and for here. And then we want to here and one here. So this is our output for this input. We basically totally reversed the matrix. Um, yes. So let make sure defined a function that does that. So it is actually fairly easy to do. And also the idea eyes that let's say that the instructor tells us that we want to reverse this matrix in place s so that means we cannot create a new metrics. And ah, also, he wants us to, for example, kind of like, um used the mutability off the off. The are the mutability in this case off python. So we will just call reverse matrix on some sort of matrix M and then in the other line, we will just bring em right. And inside here, we'll just define what s m So, for example, and will be this first matrix like this and like this, right? And, um, yeah, if I say that, Yeah, it looks good. So basically, this is the use case that we will use so inside here, we'll just accept the matrix m and inside here, we want to reverse the matrix M in place. And this is how we will test it. Um, yes. So, as you can see, the output should be this one. So what are re actually doing? Um, we are not doing anything crazy, right? We are just reversing the rose. So, uh, what we did first was reversed Those roasts, and we can just do it like this m dot Reverse ended will reverse all of those rows. So this one will be the first row. This one will be the last row, okay? Or the last list in the in this mist. Okay, if that makes sense, and then what do you want to do? It's also reverse those in the rose, right? So does does rose in the metrics. So, for example, this list we want to also in reverse it. And what can we actually do? Um, well, we can just go through all of those rows in the metrics and then just reverse it so down to reverse. And this is actually all of the code and we need to write. Yeah. Yeah, that's true. So if I run this python file and terminal you should be able to see. Okay, we get a never Oh, of course. So inside here, we need to have dose. And if I run this again ah, we get the yours out. So 654 free to one. And that is exactly what is in here. And there's so that is actually the easiest way you can do this. And this also points out to you. This is also quite common question in interviews over day will, for example, uh, call only like this reverse matrix, and then they will ask you Ah, what the M looks like in a year, right? What am looks like. And after you call the function and you need to get nothing about it and ah, see that the that this is actually immutable, right? Sorry that this is actually mutable. And that means that if you are doing something with the Matrix and here you are basically changing this one. Okay? It doesn't create a new matrix that you can use inside dysfunction, right? It only likes since a reference to this matrix. So you need to keep this in mind when you work with python and this is quite often ask in interviews, especially if you are applying for a python developer job, so keep this in mind. 9. 08 Sublist with given sum: Okay, guys, in this lecture, we'll solve the problem off sub list. That will give us a given. Some. Basically, we get a list, and we want a interrupt from this list. Ah, that will give us a some sort of some that we will will be passed to dysfunction. So, for example, we can have a list Dead Will have 12345 numbers. It doesn't have to be sorted and doesn't have to be anything, right? So, for example, they can be there can be, like, five in here and another number. And this is the sum that you're going to get. So, for example, let's say 11 and the output of dysfunction should be the interval. That actually gives us 11. So Ah, 125 is like, eight. And this is too much, right? It's 12. Ah, but two plus five plus four will give us 11th. Right. So the output should be actually index one old way up to index free. Right? So this is the output off D off disco, and for example, this should be like 100 and 10 so there is no interval that will give us the some um, we can say with we should return. Minus what? And debt bond. Maybe you can also assume that the some is actually greater, Dan. Um, then every element. Right. So we cannot have something like the some being smaller than five. OK, so it must be greater on there. So let me actually define it. So inside here, I will just type sub list, um, sub list off some, or like, given some. And we will take the list, Andy. Some as a par meters. Okay. So, list is this some is this, um then what we want to do? Well, we want to go for each index, basically, because we need to keep those indexes right. So for each index in the length of the off the array eso in the range off the lend off the L. Okay. So Len will give us the length range. Will give us a list off, starting from zero to the to this number minus one. Okay. And there we can also just put minus one in here because we know that these some must be greater than, um then all of those numbers. And with the last number, we don't have any number behind it to add it up to Right. So, um, we actually cannot, um we actually cannot solve this problem right with the last number. But if you want to keep things simply are you can just remove this. It will work. Anyway, um, that's up to you. Okay. I'll just remove it, just not to complicate. Yeah, not to complicate things. Um, yeah. Okay, so we will basically go for each and ever. Index. So starting from zero all the way up to this one and what we want to do Well, we want to basically check. Hey, does this an interval? Give us this number. No. Okay, so does this interval. Give us this number. No. Okay, so does this. Enter will give us this number. No. Okay. And then we can check even more bar. What You can also notice with this, for example, with this example on is that this is this interval is actually greater than the sum. Right? And, um, do we actually have to go through and add up those other numbers behind? Well, no. Right, if we if we know that these numbers are only positive. So that means from zero and up. We know that we don't necessarily have to add up those numbers because we won't get the sum equal to this, right? It will only get bigger, and it is already bigger. So there's no point in doing that. On the other hand, if there would be, like, something like negative number Ah, we have to go through all of those numbers. Okay? Yeah, but in this case, we have numbers only positive, so we can stop there. Okay. So, as I said, we want to check photos, intervals and eso. Let me just defined the other index. And this index will basically define how big the interview is. So, for example, when the e will be equal to zero, that means this one we will start with one. Then Jay will be, uh, j must be equal to two. Right? And we basically Adam does too and see whether it is equal to some. If it is not, we will incriminate J o K. So Jay will get bigger. And that means the interval will get bigger and so on and so on. So as I said, D j actually starts at I plus one right? Because we already have I And then we need to end at the end of the list, right? In the worst case. So like this. So basically, this range function currently takes D this number and starts the interval with this number and ends it with this number, so yeah, basically, we start with Ah, only the numbers that are behind I Okay. I hope that makes sense. And they're so we also need to actually keep track off these some of the interval. Right? So inside here, I will just put in terrible some. And I will set it in the beginning, to the number that its own index, who I right. And then with each and every Jay Wright with each and every number in here, I will just add it to it. So, like this and then all I have to do is check, um, weather d interval. Some is actually equal to s. So the summed it is required. If it is, I will just bring ah, I and J. And that's it. I can return. We can maybe even returned. True. That's up to and else. Or else if we also want to check if the in terrible some ihsaa greater or or sorry. If the s s smaller, then internal some right If it if the as is smaller weekends return falls So weekend to sprint. Ah, minus one and return falls. And OK, so we can actually just break. Yeah, we cannot just return falls because there's just one use case, right? So we have to break out of this cycle and try another interval, right? If we just returned false, it would basically this would return false because we would try it for I equals zero. And then we wouldn't actually tried for other eyes, right? This wouldn't be actually a use case, so we need to break out of this inner cycle and then try another. I okay, and, um, yeah, I think that this should actually work. And if this doesn't work, I will just bring to D minus one and return falls, right? And another thing that I want to point out is that often people kind and type this the wrong way. They usually think of it as a, um, interval some. Ah is greater than s. If you type this condition like this, it is actually a wrong way to do it. And I think that the interviewer want wouldn't be happy to see this. Um, basically, if you write d condition and if you write some ends in D condition, if you compare numbers whether it's something smaller, you always want the smaller number to be on the left. Right. So, like, this right s, it's smaller like this. So So, basically, you only have thes conditions. These these won't appear. OK, Um, yeah. So does just another thing that had one that wanted to point out. And yes, So let me actually print ah are like we don't necessarily have to print it. We can just call it eso sub list for given some. And I will just past those arguments. And as I already said, it should return one and free. Or it should bring one and free and return true. And it actually does. Okay, one and free. Um, Okay, now I have a question for you. Would this work? Um, if we have. If we have the number here, for example, if the number here can be equal to some of the numbers there would this work, you can clearly pause the video and think about it for a second. I can just run the randy algorithm so that you believe me on. Okay. Why? Okay, from once. Oof! Oh, yeah. So I also need to obviously change it here. There was kind of funny about, yet it doesn't work even though five is in here. Okay, um, if you wanted this to work Ah, what change would you make once again pause the video thing about it, Um, only have to do is maybe just put this condition in here, right? Did would actually solve it. And, um, you can just bring to I and I and yeah, that's basically it. It should work now, right? So the enter off on index to two index too. So that means this one and there it actually, it actually works. Um, yes. So I think that's pretty much it. Um if you have any questions, feel free to ask, and I will see you next time. 10. 09 Missing number in array: Hello, guys. And in this lecture, we will talk about the missing number in the race. So yet So let me start with the use case. So for example Ah, we can have array that will go like this. And we can We want to figure out what number is missing, Obviously, as you can see, um, it should be four, right? The output of this is for because the number four is actually missing in here. And, um, yes. So let's actually do this. It's not that hard to actually compute eso these. Let me once again start with the simplest solution. So let's just call at missing number, and it is in the list, right? And we know that there are numbers from one to the length of their lists, right? Uh, plus one once. Yeah, plus one, because there is one missing. Um, okay. So we can just loop for every number in the range for the length off l on. And we don't necessarily have to add the one here because the yeah, we don't necessarily have to at d one here because the missing number cannot be the last one, right? It wouldn't make sense because he would have 1234 and 56 and then it would end. There would be no number missing. Right? And okay, so we go just to the length and Ah, we can basically check if I is in. Um, if I is in Ah, the number. So in the India list Sorry. Ah, I was looking at this missing number, So if I is in the list sorry. If it is not in the list, right? We want to return I And if it s in the list, we want to move on. And then if we went through all of those numbers, we can to return minus one and yeah, and, um yes. So let me actually just try it out. So in here, I can just print the missing number from this list, and it should bring doubt for eso if I put it in here and run dis so it actually says Okay . 00 yeah, I see. Um, yes. So we want to start from one and then move to length plus one because the arrange basically returns numbers from zero all the way up to this upper bound. Okay? Yeah. So we said it to one end right now, it actually works. There's four, and yeah, it is this kind of fast solution. So let me actually go through the time complexity off this. So we have 14 cycle, and it basically grows in times, right? In the worst case, it goes end times, and then we once again check. And in the worst case, Ah, it is actually not not end times in the worst case, um, big chaos. If it is end times, we have to return it. Right? Um, yeah, we if it is, in times if we have to go through all of those numbers in list, it means that it is not there. And we can just Andy algorithm. So there's, like, n minus one. And then if, um yeah, so basically, the worst case is if the array is reversed, Yeah, if the array is reversed, um, it would be the worst case. But anyway, I think that this is, um Ah, this is and square time complexity. And in the worst case. And, um so can we do any better? Um, well, do we have to actually check all of those numbers in L while we don't have to write, Um, one of the ways to do it is maybe just build some tree with all of those elements in l. That also kind of doesn't make sense, since it is already a ray. But if the array is actually sorted right, if we can say okay, the array, assorted. What we can do is just check if I is equal to l on the index. I minus one. Right. Because if it is not equal, um, we have to Yeah, that there should be a problem, right? This should be false. And that means the element is not in your right because it is sorted. And, um, yes. So if I run this, it actually doesn't work first. Some reason. Okay, so it brings one. So Okay, so there should be, like, not in close. So like this, if it is not equal. Sorry. We want to say, Hey, this is a problem. Um, all right. All right. So that is basically how you could solve it. Now, imagine that. Um imagine that the list is extremely huge. Imagine the delist have, like, billions, billions off off numbers. Um, is this the way to do it. I wouldn't say so. Right. I think that there is a better way. And it should be with the your incursion. We should use it. We should use the rickerson. So let me actually write it. So missing number are is a Rikers in and off this list, and we also need the interest on which we are sorting it. So start and end, index right and all right, so what's the idea? Well, um, if we take a look at the middle element, right, and we know that it is, for example, bigger, uh, Dendy index. Right, then the index of the middle element. Ah, we know, Dad. Yeah, I did some number in front of it. Must be missing, right, because otherwise it wouldn't be bigger, right? For example, with this, if we take a look at the middle element, we get free, and we know that free. It's on index. Like if it is on index, I minus one. Right. We know dead. Um, there is no number missing in front of it. Right? If the Reyes sorted because there is no way you could have there isn't There are no duplicates, right? so there is no way to put those numbers in front of it. And from dead, we can kind of figure out that the missing number must be in the right part, right of the array or off the list. Right. And if the number for example, in here, we can check if the number is greater, we know that in somewhere in front of it there is the missing number, right? So that means we can recursive Lee kind of call it on the left, Bart. And yeah, and that's that's basically it. So, yes. So how do we actually approach this? So we want to compute the middle element, right? So the index index off the middle elements index off the middle element, and and this will be just the start plus end on divided by two right that will actually give us the middle elements are divided by two if you don't believe me. And let's just take the example of this. And so the started zero on the end ISS 12345 zero plus five divided by two. And it will give us this number, right? And so basically it will give us 2.2 point five and we will actually change it to integer. I'm not sure. I think it should be changed like this to end. And yeah, and And we get the index of the middle elements. So what do you want to do now? Now we want to check if the element in the middle is actually okay. So if the element in the medals so middle element index middle, right, So element in the middle, that's this one is actually ah, smaller or whether it is actually equal to the index. Middle. Right. Okay, So what did mix? Yes. So once again, let's go back to this example would close this thing. So right now, we figure out that the index in the middle is too, and that means this free, right? So we check whether the element on this index is actually equal to the index plus one, right? Because we are indexing from zero, but the numbers are starting from one. So plus one here, And if it is equal, we know that all of those numbers in front are kind of safe right there. There is no missing number, um, in front of us so we can just call this recursive list. So missing number are, and we will call it on the list right now. The starting point is actually the middle right, the index of the middle and we can even add one to it. Right? Because we know that the missing number iss somewhere around here, and, um, the end will not change. Right? And this is the same. Um, What can happen else? Well, in the else case, the number iss sexually. Ah, greater. Right. So the number is greater than the then the index and dead means that we have the missing number somewhere in the left part of it. So for example, um yet So let's say that we have called this with the first input. It will say that the index of the Mentalist is too. Okay, we will compare it. This if condition will be true, right? Because free, which is the element in the middle. So that means this one is actually equal to the index plus one right in exist too. Plus one is free. So we will call this one, and this one will basically say Hey, somewhere from this is free and This is five. So free and five will be called right. So there should be The delist will stay the same, but it will be called with free and five as a index. So inside here we get free and five divided by two, which is four. Right? And so the elemental index 41201234 That means six. Okay. And we will compare the element on the index six once again, What will or what will happen. So is the element on, um, Index four. That means this six equal to four plus one. That means five. Well, no. So we will go to this else branch and debt means that the missing number iss somewhere between the A starting point and the index of the middle. Right? So that means in here we need to put the start, and then in here, we need to put the index off the middle. Okay? I hope this this makes sense. Feel free to debug, decode and think about it for a second. And so and I think that we can even Ah, but this minus one in here? Um, yeah, yeah, yeah. And then inside here. We will basically check if these start is equal to end. And if it is, we can just print it so brained start or ends, it doesn't matter. And then return. Of course, we would otherwise just cycle forever. We would call itself forever. And wow, I'm not sure what a dis will work for a proper input. So let me actually try this out and see what are devising mistake eso if I put the are behind it and run days and okay, I forget about does those arguments. So there should be the starter zero and the 12345 Ok, so young is five. If I run this, it actually returned free. And why is that? Okay, so there is. Okay, It returned D index. Right? So it bring to D index. And some, of course, it doesn't or yet shouldn't make sure print it should just return this and we will print it then in here. Okay. But anyways, um, it actually returned the index wise that well, because it figure out that own index free. That means 012 free. That means year. There is the mistake. There was the missing number, right? And yeah, I think that this should actually work for all the inputs. So this is basically the recursive way off actually solving this problem. Um, this is oh, much harder to understand than this one. I think that in most interviews they would be happy with this solution. But some interviewers may ah want, for example, the recursive solution for this problem. And this is actually how you can do it. Basically, look at the middle element and then go either left or right, right? And this is much faster. If you think about the time complexity off this, you basically each time you take only half of the array, right? If you have no like 100 elements, right, you look at the middle one, and then you either take those elements from 0 to 49 or those elements from 51 to 99 right ? So new, basically, each time you divide decides by two. And that means you get the logarithm miss logarithmic time complexity. Right? So look and time complexity instead of a an inside here. And I think that that is much better. Especially if you have ah, huge rate and if you are maybe doing some coding interview, for example, for Amazon or Apple or Microsoft. Um, I think that they are actually looking at dissolution, and this solution is much better for them than this one. Okay, so yeah, keep this in mind and dead. That's pretty much it. If you have any questions, feel free to ask in. L see you next time. 11. 10 Pranthesis Checker: All right, So another problem that we will solve is the parentheses checker. So, for example, an input for this might be something like this. And or maybe even like this. And you want to figure out whether this is correctly parentheses, right? So district return obviously true, right? Because that's correct. And but if something actually begins, um, for example, something like this is obviously false, right? And something like this is also false because it doesn't actually complete right this disparate asi And also there cannot be, at any point more right parentheses than there is left. Prentice's right. It kind of makes sense. And yes, So let's actually write a program that actually solved this. So we will say that, um, for example, check. Let's just call the check and we'll get a string, right. This will be a string off parentheses and and what do you want to do? Is actually check for them. So for every parentheses e in and or for every character and string, um, we won't sue actually check for D. Um, yes. So we want to have some sort of counter, right? So let's just call this counter and let's just initialize it to zero. And each time this will basically tell us how many off those left parentheses are there. So maybe let's just call it left parentheses. So basically those opening right opening Prentice, see this one? And how many off them? Our industry. In the beginning, there was zero off them. And then each time, if the sea is equal to, uh basically this this thing Ah, we will just incremental. So we will say Okay, left is now greater, right. There is one more Prentice e. And if it is not in this case, let's just say that, uh, every out of French asi must be the right Princess Brent Asi in the input string. There are no other characters. Okay, so we are just sufficient with the else branch. Otherwise, you would just check if d. C is equal to the other Prentice. See if there would be some other characters. If there would be a lot of characters, You can actually filter these parentheses out in the beginning and yet, but you definitely want to ask your interviewer dead. Whether there is, like, some sort of maybe some space in there, right, or whether there's something or whether there are only those two characters. Okay, Yeah. So let's just assume that there are only those two characters. And so what happens if we reached the right or the closing? Prentice E. Um well, we want to de crim and left, right? So it will be minus equal. Ah, one. Right. And then, um inside here we can just return. Whether left is equal to zero. If it is equal to zero, that means it is correctly. Yeah, it is correctly closed. Right? And if it is not equal to zero, that would mean, for example, this case, right? Imagine it. So, uh, we start off, then left is equal to one, right? Because this this is one left, then diverse The second left. So it does he go to two then we d crimen one. So that is left is equal to one and then we need to return. False and left is currently go to one. So one equals zero is false. So we will return false and Yeah, but this will not still will not work. Maybe you can think about for a second about the use case that will not work and feel free to pause the video because I'm about to show you eso the U. S case could be, for example, something like this. This is just a simple use case. Ah, and it actually wouldn't work. It would Our algorithm would currently ever turned true, right? Because it would say Okay, Ah, left is equal to minus one. Then left is equal to one, right with the 2nd 2nd character. Okay. And we would return True bad. We differently. Want to return falls? Because this is not properly Ah, those are not proper proper parentheses. Right? And so how do we actually fix this? Well, inside here you want to check if left is equal to zero, right? You can also write if not left, right, that's up to you. But if it is equal to zero and we have, um right breath, Asi Ah, we definitely want to return false, right? Because there is no way, um, that those parentheses are correct. And currently it should work. So if I just, uh well, I need to print it out so that we actually see it. So bring D Check off. Let's say this one. I think that this should be true. If I road, it's correctly. And if I run this, it says true. Okay, that's cool. And yeah, let's also do the check off Those can etch cases. And so, for example, it's just removed this one, and I think it just removed both of these, right? Yeah. Um, like this, I'm not sure whether it works. Yeah, so this is not properly right. There is one off them. One of the left ISS. There's more of the deuce left ones. Right? And let's also do distinct so something like this and check whether we get true and false and false, and we do true false, false. So, yeah, it should make sense if you take a look at the code. Um, in my opinion, it's actually fairly simple. I don't think that there is a better way to do this. Um, you could use a data structure, but in this case, it iss um, it is maybe easier to countess. Um, yeah, but you could use just some sort of qui and or stack and just put Deuce Brent theses up. And if there is the other Prentice eu, you just but one of them up right. It's simple as that. And if you pop something that is not in there, it would basically mean this each case. Okay, Yes. So I hope does make sense. And if you have any questions, feel free to ask in Al soon next time. 12. 11 Stock Buy and Sell: Hello, guys. Welcome to this lecture. In this lecture, we will go through a example off stuck, buy and sell. So in this problem, the interviewer will tell you that you have a list off values, and those values are basically stock prices. So basically how much the stock was worth that particular day? Or maybe second, it doesn't matter. So you get a list of values and you should write a function that will return you a bears off values. And the first part of the pair is a index where you should buy. And the second part is the index very should sell, right? So, you know, barely from stock market. Dad, you should buy the lowest possible price and sell at the highest possible price, right? And And make some profit, make the biggest profit. And then once again, when it drops down, you want to once again by and then once again, still high. So, um, just to just to make sure that you understand it correctly, let's say that this to say inputs. So for example, 23 12 34 55 22 44. And the out good, right? As I said should be pairs. So we can, for example, printed it doesn't matter or return a array of Paris really? Doesn't matter. So let's say that we just want to print it. And in this case, um, yes. So should we buy at the index zero? Well, no, because the stock price went down. Right, So we should buy at index one. Right? So that means for $12 then it goes up and up and we should sell at index free. If I come to correctly. So sell for 55 then once again, weight and the second by should be at index for. And the cell should be at index five. Right? Then you wait. Ah, the stock price drops. We buy once again at this point and sell at this point. And, um, yes. So this this should be the output or dysfunction? Um, yeah, I hope that makes sense. So once again, if you don't know at the Rial interview, if you don't know something, just ask the interviewer. Right? Really? Really asked a lot of clarifying questions. They really want to see you asking some sort of questions about e problem. Okay. And yes, So let's just now assume that we get everything correctly. Eso Let's just solve the problem. So what do we actually want to do? Well, um, first of all, we should know, um, whether the price is going up. So what? What are we doing? We are buying at the smallest brides, so, yes. So let's assume that we found the smallest Bryce. When do you want to sell? Um, well, we want to check if the price is going up. Right. So if if the price the next day is greater than the price of the previous day If it is, we want to keep buying, right? Or like not selling on. And we will still move on and compared the other number. Right? So another day still is greater than the previous day. Then we move on and compare this day to the previous day, and we see that it is smaller. Right? So when we see a day, uh, So let's just say that day when brize drops right, we know that when we compare those two values, right? So, in other words, uh, uh, price is smaller than the previous day. And so what do we want to do? Well, we would like to sell. So that means we would like to sell the previous day, right? And yeah. So that's basically when we want to sell. Now, when do you want to buy? So we would like to buy. For example, in this case, we don't have many options. So if I just add something like 18 in here and then something like 15 in here Um, yes. So, uh, when do we want to buy? Well, we want to buy a d lowest price. So once again, we go through those numbers and check if it is smaller. Right? So, um, if the, uh next day d prices smaller So, uh, you want to buy when? Um the price of the day is smaller. Dendy Previous day. Uh, sorry. Sorry. We want to just move on. Right? Sorry. Sorry. Uh, yeah, that's mistake. Eso We just want to move on right to the next day. If the price today is smaller than the previous day, right? And then we once again move on, compared this Okay? Still a smaller than the previous day. Runs again. Move on. Compared toa those two smaller than previous day, but Wendy Price gets bigger. We should buy the previous day, right? So if the price today is bigger than previous day, uh, we should have by the previous day, right? Okay, So let's actually write a function dead. Does that so deaf by cell? Let's call this one and we will have the prices list. So let's just call it prices. And so what do we want to do? Well, we want to go for price in prices and, um yeah, and as I said, we need to First of all, the finding buying price. So, um, how do we actually implement this? We need those two values. Okay, so we need to initialize it to, for example, something like, I'm zero. It doesn't matter and then sell. And, um yeah. And, um what do we want to do? We want to First of all, compare d current price. Eso if the brize ihsaa Ah, smaller than the prized the previous day. So previous price. Okay, then at the end of days, we need to set it so previous price will be at the end of the cycle, right? The previous price will be equal to the price off today's right, because then we move on to the another day. Okay, I hope. Didn't make sense. And so, yes. So if the if the previous price is smaller, sir, if the price is smaller than the previous price. Ah, what do we want to do? Um, well, if we have a bi right. So if we have defined by, ah, we want to sell. So that means, um, we would like to sell d prove. Is they? And also, we would like we need those indexes right here. So we want to print indexes. So in order to do that, I will just write animal, right? And this will basically create a pair off index and value. Okay, so in here, we can just type index and price. So prices devalued. That is in the list and indexes the corresponding index, and we will just it right for it. And yes, So if we already barred Okay, so if we already bought, we would like to sell. So, um, so if the by is some sort of index. Okay, So I will just bring, buy and sell like this, and okay. And yet and another thing that we need to do is, uh, the finding, Elsa. So else, if the price is greater than previous day reverse price, Um, we would like to ask, Right? Wendy, price is greater than the previous day. We should by right. Okay. We should buy the previous day. So if there s a mm. All right. So how would we go around this? So if by is defined, um, Okay, so if by is not defined So if, ah, if we don't have defined by we will set by to the previous day. So that means index minus one. Okay. And the cell in here should be once again index minus one. Right, Because sell the previous day the previous day is index minus one. I think that should make sense. And yes. So if we, uh, don't have the index when we bought, we want to buy. OK. And, um okay. And this should make runs against sense if we ah, have the index. Ah, when we bought, we want to sell when the price drops. Okay. Okay. I think that this should make sense. So right now, we also need to define the previous price. And let's just say that it. Zero. Ah, it should be something so that we don't buy a differs the necessary. So, um, the price should be grader. Okay, So the price should be actually smaller than the previous price, right? Um, yeah. Yeah. So we probably want to add something like a max and value here. Okay, So for now, I will just put something like this in here, and and yet I'm okay. Okay. I think that they should make sense. And here we also need to now said the by two, for example, false or like, zero. I think that this should work. And then we said the previous price to Price. I think that this should actually work. Um, if I actually print the result of it so by so, uh, over disarray. Wow. Ah, I added some. I've added some numbers to it, so I think those indexes will be different than those that we get in here. So if I run this, it says free and five. Okay, so we go 012 free. Okay, So we buy a does lois point and sell at this point. So five. Um, that's great. Um, all right, so what? Actually happened? Well, we actually bought at this born and then went to this point, right? And inside here, we sell bar. Um, when we are selling, we are actually, the index is this one. Andy prices this one. Okay. And because the price is smaller than the previous price, the previous price is 55. And we have defined the by, um, we actually print D by and the index and then we sell. We said by 20 and we said the previous price to 22. Right. This will be skipped. So what is the problem? Well, we don't catch the last last kind a bit, right? And here we should also buy and then sell in here. Um, So what happened next? Well, we move on to this day. Eso 44 d previous day is 22. So we g o s price. Ah, smaller dandy. Previous price. No, it's greater. Right? So the price is greater than previous price. Um, once again, you may notice a mistake in here. It should be like this. Okay, So is the previous price smaller than the price? And so Ah, yeah, yeah, that's true. And if we are not buying. We said by 20 in here. So we are not buying. Ah, we should actually ah said by two index minus one, right? Um, yeah. So this is what happens. We said we are not buying right, because by is equal to zero. And we said bye to basically this day, OK? And then what happens? Well, we just break out of the cycle because there is a break out of this four room, right? Because there is no out of atty. I hope to make sense. So, um, what do we actually need to do? Right? We need to fix this problem. We need to, uh even a d China with the last number. Um, yes. So maybe at the end, if we have defined so inside here, we can just check if we have defined by right. Ah, we just want to sell at the last day, right? Because that's like the possible the last possible day to sell it. Right? So if we have defined by, um, we just want to Brent Ah, basically this thing, right. We want to print D by and then the length off the list. So link off the prices minus one. So basically the last day, Okay. And, uh, yeah, I think that this should work. We didn't even need this cell. So if I save it and run this one's again, um I think that this should work. OK, so why is there to none? Okay, I see. I print I print inside here also, so that shouldn't be here. Um, if I get rid of it like this, it should be better about anyway. So what is happening now? We are buying at index free. Okay, so at 12. And that's correct. We sell at 55. That's correct. And we buy at six. So that means 22 then sell at you asked one yet. So the algorithm is currently working? Um, yes. So the previous day should be we should define the previous price. A xamax end. It depends on the on the on the programming language you are working with, um, but usually at the interview, it's You are fine if you just ride Maxence. Even if you don't know the proper constance, they are fine with it. They mostly want to figure out whether you are able to actually solve the problem on not whether you are able to remember all of the constants that are in the ah, in the programming language. Right? So usually, uh, this world would find, um okay, so I can just take a look at decode whether weekend somehow improve it. I think that this one iss uh, quite a fella. Easy. It's asked to actually solve as long as you are able to kind of defined dose to conditions , right? Um, yeah. Then then if we have defined you buy and if we didn't define him by, um, this may be a bit of ah trouble for you to to actually tried to think about this for a second. Also, a lot of people would forget to set the bite a zero once you print. Okay. Eso That's another thing that you may want to keep in mind. And yeah, I even I forgot on this last conditions. Um, yeah. So, usually the interviewer, if you forget, for example, in something like this, the interviewer will tell you that Yeah, he will tell you usually because you write it on ah kind of white board or something like that or piece of paper. He will tell you like, OK, so you go through this, then you said then you sell here. Didn't buy here. But do you sell? And you always when he asked you something like this. You want to think about what is wrong, right? And you need to go through the code, and they really like when you go through the code and actually saw them from the cold and kind of evaluate decode as a computer. What? Um, then then if you solve the problem, usually it's family isn't ask too soft, and usually David kinda even give you a hint, if you don't know. So don't be worried if you somehow misstep or something doesn't work the story. Fine. Okay, so that's pretty much it for this video. 13. 12 Number of leaves in a tree: All right, gas. Welcome to this lecture and this lecture. We will count the number of leaves in a binary search tree. So in order to do that, I just quickly wrote a simple banner research tree. So we have the note class, Okay? Where we have where we can initialize it with some sort of value. And then we have a binary search tree. We initialize it with some value. We set it to root, and yeah, and then we can insert. I didn't wrote any other functions because we don't actually need them. We just need to insert values. And yes, So this is the simplest way to actually write it. So this is a recursive function. It calls itself either to go right or to go left. And if there is no child, it just inserted the devalue that we want to insert. And if it is already tree it already entry, it actually brings it out. And yes, So what's the actual What's the actual Ah, use case? Okay, so we, um, inside here we just imported divine every surgery and and created a new tree, and we inserted some values. So we have 10 as a route than five is in the left sub tree. Okay, so that it's one leave, right? Leave is a note that have no other child's. Okay, so no dead have no Childs is a leave. I hope that kind of makes sense for you. I think that you already should probably know that if you know what binary search tree is. Um, yes. 05 is a leave. Then we have 15 and 15 half as a left child. 12 and then 25 is a right child. Right? So 25 12 are also leaves. So overall, we should get free leaves right for this particular tree. Um, I hope that you are able to actually see this. Ah, Okay, so let me actually ready functionality inside the tree. So, inside the binary search tree, we will define a method call number off leaves and CSO inside here. Let's just define it. So defined us as number off leaves. And, um yeah, let's also let's do it is recursive Lee. So we will have a node where we actually start. And when where we are at and eso inside year, we will just past the route, writes a tree root and yeah, And what were on? What do we actually want to do? So we want to sum up, right? So we want to sum up all the leaves that are in the left sub tree off the note and in the rites of tree off the note. Right. And yes. So So let's actually do that. So if we have, uh, so if the note have the left and if it have the rights of tree, right, so if you have both of them available ah, we want to sum them up. So we just want to return. Um, the number of leaves. So eso myself. Yeah. Also, I forget on self in here, so self a note and we won't self the number of leaves on the note that left glass. Okay, so plus, and pretty much the same thing, but only this time on on. Know that, right? Okay, so this is basically what I just said, um, we want a Okay. I cannot put this on separate line, so it will be hidden in here. Okay, So did looks terrible. Um, yeah, OK, but you already know was there, right? We want to if the node have left and right, child, we want these Some, uh, some of the leaves in those both sub trees. Okay, I think that it should make sense. For example, 40 route we have 10 and we want some off the leaves that are in the left sub tree. There is only five. Write the note. Five is a leave so that it's one plus the number of leaves and the right sub tree. And there there are two right, 25 is a leaf and 12 is a leave. Right? And yes. So when we sum it up, we get free. Okay? I think that this should make sense. OK, So what should happen if we have, for example, only left sub tree? So if note have for example Ah yes. So only left sub tree. That means the right is false, right? Ah, yes, Yes. Sorry. Sorry. So if the node left is defined Ah, that means it has only left sub tree. And ah so what is in the right sub tree? Well, in the right sub tree there are not any leaves, right? And the grand note is not leave because it have left sub tree. Right, So we just return. Um, basically this thing We were turned the number of leaves in the left sub tree, right? Ah, And there should be else if right so else if we returned the number off notes in the ah, let's a tree and then if there is right, Okay. So if the node have right Ah, we want to return the number of note the number of leaves in the right sub tree. Right? That should make sense. If there is only one sub tree, for example, the left one is missing. We only want to count those child's those sort of those leaves in the right sub tree. And yeah, OK, so what can happen next? So we either have left end right sub tree. We either have left but no rights up tree. And then we either have right sub tree or no ends end no left sub tree. And what is the next possible thing that can happen? There are four possible scenarios. Well, the next one is that we don't have left and we also don't have right sub tree. So inside here, I'll just type else, right, because there's no other possibility. And do you remember what is a leave? Well, leave is they know that have no left and no right sub tree. So basically, this mean that it is a leave, Right? So yeah. So in here we just want to return one. Right, Because this is a leave, right? This is the result for this this part of the tree and this is our function, actually. So this simple kinda four branch if takes care of the number of leaves. So if I just saved this thing and actually run this thing, um, you should be okay. I should actually bring this out. So sorry about it. So print the number off leaves, and if I run this once again, something OK, I didn't save it. So let's try it one more time. And there are free sub trees. Um, yeah, but in this case, we don't actually test this scenario where the no doesn't have left sub tree or rights up to you. Right? So we also need to insert, for example, some, um some some value that is greater than 25. So let's say 35 eso dead would mean that there are still free leaves because 25 is currently no longer a leave because it half right sub tree. Where is 35 But in the left sub tree off 25. There is no note. Right? Ah, so let's see whether it actually returns free. So if I run this again, it's us free. So it actually works. Basically, uh, with the 25 when 25 is the current note. Ah, the condition. Uh, this condition will be true, right? Because no left is zero. Right? So this condition will be true, and we will return only the number of leaves in the right sub tree. I think that this should make sense. This is fairly simply, ah, way to actually do this. Um, what can happen next is that the interviewer will ask you to actually tell him the time complexity Fordice. And so what is the time complexity? Do you have to go through all of the notes? Um, yeah. You have to write. You have to go through all of the notes and, uh, yeah, and I don't really see a ah a better way to do this. Ah, Ready? So, yes. So the time complexity is over Fan when and where is the number off notes in the tree. And, yeah, so there's pretty much it for this lecture. 14. 12 Number of leaves in a tree (using loop): Okay. So another thing that the instructor may ask you currently is that you solved the number of leaves. Why a Ryker shin? Ok, where you basically start with a note and a new county left and right sub tree and recursive lee basically figure out the result. Okay, but he asked you to stop the rickerson. Don't Don't use Rickerson to solve this problem. Eso you have to do it where? A loop, some sort of loop. And the cool thing is that every loop can be Riverton into a Ryker shin and ever recur Shin can be Riverton into a loop. OK, so that is a important thing to keep in mind and maybe even take away from this lecture that every loop can be Riverton into a rickerson and ever occurs in can be reverting into a loop. Um, yes. So let's actually do it. So ah, let's just define the number of reliefs and I as a hitter tive and we'll just bear self. We don't need it. We don't need anything else. And, um So what do we want to do? Well, we want to just keep track off all of the notes, right? Go through those notes and basically figure out Add all of those child notes, right? If we go for a note, If he has a child note, add it up. And if he doesn't have a child note, um, it is a leaf, right? So we just want to increment some sort of counter. So leaves the counter bees Bill started zero. And then we will have the array off notes, and it will basically start with only one element. And this will be the root. And you want to, uh, g o right. We want to loop while the while there is a note, make sure the attribute. I can write it this way. Let's see eso while there are notes right in the array. And, um so what do we want to do? Well, let's just say the first. So let's just say note, the Quran note will be equal to the 1st 1 it promotes. Doesn't matter which one you take. Ah, but we will take always the 1st 1 And what do we want to do? Well, we would like to check if the note is child, so if it half the left, right, So yeah, well, first of all, we can We can do it Sort of similar way like this, right? We check if it has left sub tree and then recheck if it has the right sub tree and else Ah , it is a leaf. Right. So we would increment encounter. Um, yes. So with those conditions, there are a couple of number of ways you can actually write the condition. Um, bar. In this case, I'm not sure whether we can write it somehow differently just to show you. Ah, yeah, I think we can. But it wouldn't be. Yeah, we can. We can do a different list. So if the there is a left sub tree Ah, what do we do? Well, we just add it right. So we added to Ah, the number Judy notes. Right. So inside here, we have already knows that we go through. So we just append to their the left the left note, right, the left child. And then we also need to use if, Okay, so we cannot use else if and currently we want to take a look at the right. Right? So if there is right sub tree, we would also like to add note, right? Why cannot we just write else if maybe pause the video and think about it? No, it's fairly easy because imagine Ailey Imagine a note that have both left and right, child. Right, So we want to count. We want to go through both of these, right? And so what happens? Go through the killed. If the note left, if there is a left node, we will add the left note and then we will just jump away. Right? Because this is a else if branch it will own execute if this is false right? And we also want to add the right note So Ah, that is why there needs to be an if and then The last thing is, Dad, it is a leave, right? So you want to actually Ah, yes. So we actually want to check if it is a leaf. So if, uh, there is no node left And also there is no note, right? So Ah, right. So not no left. And also not ah node, Right. Okay. Like this You can even change those conditions Two or eso No left or note. Right. And then not in front of all of this Bremer doesn't matter a lot of ways you can write it. And yes, So if that is true Ah, we want to incrementally number of leaves, right? So leaves will be plus equal one. Because this is a leave note. The note that we have taken as a first from the array is a leave, and the last thing that we're going to do is delete. Right. So the lead, the ah, first they're laid the first element from the notes array or notes list. And I think that this should work so we can just then return the number off leaves like this. And so let's let's try it out. So if I take this one out and just print it with with the I okay, and let's remove this thing and let's run this thing, um, it actually works. Okay, so we have free and free the number of leaves. Yeah, if I go through the code once again, D point as dead. We want to go through all of those notes, and we want to basically, each time we visit the node, we want to add up dose. Ah, no. Those child notes, right and Um, yeah. And when we add up those child notes Ah, we want to also check whether it's a leaf, right? If we don't add any of those channels, we know that it is a leaf. Okay? And lastly, we want to delete the note. Otherwise, we'll just ah liu forever, because the notes, uh, would just stay the same, right? And so that is basically the it's right of way of doing things. This is a recursive way of doing things. Um, it is It is also something to do with a graph search if you know, depth. First search and breaths. First search. Uh, this one is actually the depth first search. Okay, Because we are going to the left and then left and then once again, left, right. Imagine that we have a binary search tree, and there are It's filled with notes. Okay. Eso inside here. If the computer executes this cold, it actually wants to return this. Plus this bar it actually, first of all, needs to figure out what is this? So it actually calls number of leaves on the left child. Okay. And then with the left child once again do the same right and so on. And then when it reaches a leave, it kind starts to backtrack and start to figure out those right Childs. But on the other hand, with this approach, you kind of go step by step. So you go like this, You take the first note, and then you grab all of those its successors. Right? So all of those nodes that are directly connected to the 1st 1 right? And then you do the same for dose knows that are down, right and so on and so far on. And yes, so these are basically the two ways against search in a graph. Uh, it can be used not only to trees, but also, for example, if you have graph off any sort like they can give you a road map. Road map is basically a graph. If you think about it and you can either go start going, uh, with the breath first, right. So you go. You start at some point and you gradually go in all of those directions, right? Or you can go deaf first. So that means you start with this and you go, like, one way, and then you check the other way. Then you check the other way. Then you check the other way. Right? And you go like this. Um, yes. Oh, yeah. That's pretty much it for this lecture. If you have any questions, feel free to ask in Al soon, Exxon. 15. 13 height of a tree: Hello, Gas. In this lecture, we will actually go through the how to compute the height of a tree. Right? So the height of a tree is basically Ah, how many times you have to go left or right in order to reach the most further relief. Right? So the leave that is that is the furthest from the route. OK, so for example, in this case Ah, we have the route 10 and the most further leave is 35 right? We have to go first to 15 from 10. We have to go right to 15. Then we once again have to go right there is 25. So that is to and then we once again have to go right? And we reach 35 OK? And thats so basically they may ask you how do you actually compute this? So how do you actually computers? So we just do we just define it so height and we will just take the self And actually, I think the starting note Yeah, I think we should take the note. Right. So, um so what is actually the height, right? What is it? If we have any note how do you define a height? Um, well, how it is just a one. Plus, uh, the bath to the most Firdous leave in the left sub tree or the path to the most first leave in the right sub tree, right? It depends where the most further leaf iss. Right? So basically the maximum from the value that we get from left and right sub tree. Right? I think that this should going to make sense. Um so if we are about to do this recursive lee or I'll just writing goat again, it pretty much doesn't matter. So if we have the left and if we have the right sub tree Ah, we want to just return one Blas de maximum right? The maximum off those results that we get And what do we want to get? Well Ah, when we called the height on the left sub tree, right. And then when we call the height owned the rights of tree right? And so that is basically what are we what we are doing, right? We try to and 12 d maximum from the left and right up tree. Ok, and OK, so the another thing that can happen is else if there is just the left sub tree. Okay, so what do we want to do now? Well, we just want to return one plus the height of the left sub tree. Right? Because we know that the height of the right sub tree is currently zero right? The height of the right sub tree zero. And so that means, um that means we only have the left sub tree, right? The height of the sorry in here should be left. The height of the left sub tree must be greater than the height of the right sub tree. At least one right. Ah, and then we have another else if. And this means if there is a right note once again, we want to return one plus the height off the note on the right. Right. I think that this it makes it feel free to debug this killed and actually figure out how it actually works. Um, right, we can, even for example, if you don't understand it, we can even bring to those numbers. Okay, So, uh, let's get back to our example. So in here, we already defined what we need to do if there isn't left and right up tree if there is left. And if there is only right now, we also need to define What if there is a leave? So if there is a leave Ah, it just we just want to return the same thing as here. Right? So we just want to return one plus the max off the left sub tree and the max off the right sub tree. And both of these left is zero and write a zero because there aren't any right, So we just want to return 11 plus zero is one, right? Um, yeah, and I think that this should actually work, so if I just ah, try it out. So if I run this run this file Ah, as you can see it, prince, for eso If we g o then that it's one, then we go 15. That is to then we go 25 days free, and then we go 35 Dennis four. Okay, so that actually makes sense. Because the hide off a, for example, only a route if there's only a route this one, okay. And the height of a empty tree zero Um okay, so it actually works? I'm not sure. Where do you, um, reading know how it actually works. So I was trying to explain it a bit on and I will just bring to bring down those numbers. If you already know what is going on, feel free to just move on and play the template. Another lecture. If you are not sure what is going on, I will try to explain that the bet. So inside here I will just brained what is happening. Okay, so I will just Yes, pretty much Doesn't matter. I can just I don't necessarily have to story out, So I will just put it inside here so we'll print each time We will bring the value of the note that we are currently at. And then D Max from the, uh either left or the right sub tree. Okay, then inside here, Well, brain once again devalue. And then the height of the left sub tree, right? And then inside here Ah, we can just print once again the value and the height of the right sub tree. And then inside here, I can just bring devalues, so note Well, okay, so if I run this file once again, As you can see, there are a lot off a lot of things that are that are actually printed out. So, um yes. So what is actually happening? Well, inside here we are, actually starting with 10. Right? And we call this right, We want to print it out. But ah, computer doesn't know what this means, right? So he just goes this function again and again. And ah, on the left sub tree. Right. And with this tree, the left sub tree is only five. OK, so ah, then five sprint it right. So inside here, that's this print. Okay, five sprinted. Uh, then another thing that is happening ihsaa we go back and we know that the dis Max is one. And we want to figure out what is the height off d of the another one Right off the off the right sub tree. Okay. And s o that means we go to, uh, 15. Okay. And then in 15 we need to once again do the same, right? It's still have left and right, sub tree. So we go left and there's 12. So that is why this 12th is printed. Okay. On a then we go back to 15 and we go to write it. So because we want to figure out the maximum right from left, we get one and what we will get from right. So when we go right, we will have 25. Okay. And 25 is still not a leave, right? It's still have the right child, which is 35. So we will add one plus the height of the right child, right? The right child don't have any notes, so Ah, basically, we will return one. Okay, so this 25 will return one plus one. And in this 15 we will basically check. Uh, we will return one plus the maximum from left, which is 12 which is sorry. One right from the 12th or D maximum from the right, Which is Ah, to because we have 25 then 35. Okay, So what is the What is bigger? One or two? Well, to write the rights of tree, have more have higher height if if that makes sense, and they're so you returned that. Okay, So that means inside here. It's the first return, and then inside here. We just printed out, right? So d 15 have d to the max is equal to two, right? Because one is from the 12 and two is from the 12. 25 plus 35. Ok, and then from those 15 we go once again up and ah, yeah, we get to OK where you are. We get to 10. Okay, Andy, 10 have basically ah de Max or free. Okay, because ah, we have the right sub tree. Right? And with 15 we have the height, the maximum might off Jew plus one, which is free. Okay, I I hope that this kind of makes sense. Um let's see if I can print it out. Maybe in a different way. So inside here I Rojas, Right, Height of the left. Okay. And then I will write height of right. So eight off. Right? And those are Yeah, this is basically what we are doing. We are adding one to the to the maximum off the height off left sub tree and the height off right sub tree, Ok? And yes, if I put another thing here and removed this and I will also remove those things because I think that they over. Yeah, they are complicating things a bit. And if I run this again, I think that this should makes a bit more sense. It should be, uh, kind of more clear what is happening. So if I go, fruit is once again, Um, yeah, with 15. Okay, with 15 we know that there is one child, right? And the left sub tree, which is 12. Right? And in the rites up tree dearest 25 then 35. Okay, so there is the height of the right sub tree is to write, which is set in here only. There is aces. There is a typo, but the the height of the right sub tree is too. And the height of the left sub tree is one. Okay. When we go to 10 right when we go to 10 what is happening? They're well, the height of the left sub tree is actually one. Okay, because there is only five in there and the height of the right sub tree is actually free. Why? Um, well, because we have the 15 and the maximum off 15 is actually too right. NT 15 returns just maximum off these values plus one which is free. And yet so do you. Total result. It's actually four. I hope that this actually makes sense if it doesn't feel free to ask some questions. Ah, yeah, and I'll see you next time. 16. 14 are trees identical: Okay, guys, welcome to this lecture and this lecture we will talk about the Are trees identical problems. So basically, we want to solve the problem or figuring out whether to beina research Trees are the same. Okay. And if they are the same, um, we want to return true. And if they are not the same, you want to return false. And we cannot use Riker Shin for this problem. Um, yes. So you already know that we can do it do things either with Ryker Shin. Like, for example, the height or alternatively right on de. So let's do this one with the loop. Right? So I'm not sure how I called this function is identical. Okay? And so it's identical, and it will accept the object. And also the route off the other tree. Right? So the root of the other tree. I don't know how to call this one. So for example, second route. Okay. So now what do you want to do? Well, remember how we went through the tree like this with when we count the leaves, right? We want to do pretty much the same. Only this time I'm going to go through two trees at the same time. And each time you want to just compare to notes to each other and whether they are identical. So let's do it. So inside, he will just have the notes. One for example. Let's call this one. And this will be a ray that will contain the route off this crane note. Right. And then we will have the notes to which will be a array that will basically start with the route off the second tree. Writes a second route. Basically, this thing that it's past and yeah, then we're going to just look while the notes one or notes to right, Because yeah, yeah, or like we want to. How do I put this? Um, because there can be problem if we check it this way. There can be problem that, for example, no notes. One is empty, but notes to still have a elements or yeah, or maybe not. Right, if you really think about it, if you imagine this, um, can there be a case? Actually, no. Right, Because if one of them is empty, that means we went through all of those leaves, right? And if we check every note and whether it is the same as the other note, we would actually figure out that those notes are not the same. Right? Um, I think that this should make sense. Or maybe we can even do it a bit differently, but it pretty much doesn't matter. Eso we'll basically go through all of those notes while there are notes. And what do we want to do? Well, we will just take the first note. Ah, which will be eso? Basically we will take the first element from the notary notes One array and we will just depends to the end the left child. So know that left and then appends to the end the right child. So notes one append and then do you know that, right child? Okay, so we basically take a note and at the left and right child. Also, another thing that we need to do is check values, right? So we also need to have the second note and it will be from the notes to and once again in leg zero and we want to check if note value is equal to note to value right? And if it is equal, we just move on right with our computations because the values are the same. And we would like to insert to denote Wandy left child and the right child. And then we would like to insert two d knows notes to once again, the left child and the right child from the notes, too. And you need to keep in mind that the ah, the order matters. In this case, if we would insert the right child first, we will get an error, right? The are we would return. False about the D trees might be identical. So we need to insert dose dose. Child's in the same order. Okay, so we insert them eso left and right. And, um, yeah, and then if they are not identical ah, we can just return falls like this because they are not identical. The trees cannot be identical. Right? And what else? Um, well, we need to delete those things, right? So delete, uh, notes one at in the zero, and once again, delete notes to add in the zero. Okay. And I think this should actually work. Um, and there is the problem that I just talked about, right. So with this while while loop. Um, because currently we, for example, we the imagine that the we have a tree and the 1st 1 have only route and there is, like, 10 right as a as a route. And with the 2nd 1 there is once again 10 as a route. But it has a right child. Right? So five is a a route. And, uh, yes. So with what this coat actually work? Well, we start with notes. There is 11 note, right? And with notes to there is also one note. So this is true and we take them up. The values of them are equal. So we just add those childs up, right? So notes to will have the five there and we delete those things. And then we go once again to this vile loop, right? And the notes to still have one element right in this five, but knows one is empty and then would mean that the this line would get us an error because we are trying to grab an element that index zero. But there isn't any right. So would this thing actually solve this problem? So there needs to be node one and no. Two. Well, yes. And then we also need to check at the end of this. Right? So this would give food the example, and this would be false, right? Because no, do one is false, Right? Because there is no note and notes to is true because there is five. OK, but there is a end and force, and true gives us force. So we would break out of this cycle. And in here, well, you would like to return whether they are the same, right? So whether the length of the nodes one is equal to the length off the notes to right. And both of these has to be zero. But both of those length has to be zero, and we don't necessarily have to check whether they are zero. Because at this point, we know that at least one of them is zero. Because otherwise we wouldn't break out of this condition, right? If both of them would have elements. Ah, we would still be in this cycle in this loop, right? And yes. So, um, this is the code that should actually do the work. Um, so let's try it out on this example So if I run this file, um, it should return True. Okay, We get an error, Um, object to have no attributes of out. All right, so, huh. Okay, so there is a entered your object. Okay. Come home. Hm. This is this is a tricky one. I'm not sure what is happening. Maybe I'm eso I'm adding the left and right child, so you should be notes. Um All right. So no to node one. Um, yes. So the problem is that one of those notes is actually an in teacher. I'm not sure whether d rude when we best It should be a notes. Wow. So this is this is a weird one. This is really a weird one. Um, so yeah, so let me try to debunk the coat. So using control and five. And let's just yet it's usually a thing that you want to do If you get somehow a buck, that is quite the weird one. All right, so the note is actually zero and the second notice also zero. Yeah, I know. I know. What's the problem? All right. So if you know what the problem Waas Ah, you good for you. Um if you didn't, uh that's okay. I also don't know. I forget to actually check whether there is a left or right child. Right. So, for example, imagine the denote is a leave, right? We would still add the left and the right child, but they are just zeros, right? Because they don't exist. So inside here, we basically need to add those checks. So if there is the left child Ah, we want to add it. Okay, on so on. So if there is the right child, so note, right, we don't add it. Right, so on. And if there is the note note to dad left. Okay, we would like to once again add it. And if there is the on again note to that right, we would like to add it. So inside here, let's just add it up. So if I run defile again, it should work now. Sorry about it. And if I run this, it's is true because those two are identical. If I, for example, into the 2nd 1 I insert a new leaf. Ah, with value, for example, 45. Uh, currently, it should return falls. It does. Okay, so that's cool. And if I, for example, remove this line and change something in here, for example, this 12 to 13 and run this again, it should once again return false. It does. OK, so it seems like it's working now. Um, sorry about it. Just you need to just check whether you are adding actually something, whether there is actually the left sub tree, but it every say a note in there. And if there isn't any, you don't want to add it, right? Yeah. Um but anyway, decode seems to work just fine. Ah, if you have any questions, feel free to ask, and I will see you next time. 17. 15 Sum up numbers in a string: Hi, guys. Welcome to this lecture and this lecture. We will actually go through the summer off the numbers in a string. So, for example, the input, maybe something like, Ah, 22 whatever free and four. And the output of this function should be the some off those numbers that are appearing in the string. Right, So in this case, it should be 22 plus. Ah, free blast four. Right? And it's like, no 29 right? Um, yeah. Okay, so let's actually do that. This this is quite common form for interviews at, for example, Amazon and other companies, like s A B and stuff. Yeah. Yeah, this is quite common to have a coating interview. So let me actually go through and solve this problem. So let's just define a function. So count, um, count numbers. Ah, and it will take the string. The input string. All right. Like this. And some. What do we want to do while we're going to go for every character in that string and we want to check if it's a number. So if the character like, for example, if zero is smaller or equal to the character and ah, the character is smaller or equal to nine, right? Um, yes. So make sure you if you write some condition like this, makes you write it this way, right where you have on Lee, you need to have only those type off type of comparison, right in the if condition. Okay, um then what do we want to do? Well, um, we have some sort of number. Um and yes. So there are a couple of cases, right? We can have a character that his number, but it it's like some following number with this 22 righty. Or like if I put free inside here, be free is behind the two, right? So we basically need to compute some temporary number, right? So some, let's just keep it temp. And this will basically be the number that we are currently counting. Right? Andy attempt. Ah, Will be currently, when we add a new character of what do we want to do? Well, we want to multiplied by 10. Right? So that means basically moved those numbers by one year, but by 10 basically, and by one digit, if you want and then at d c. Right, so, plus equal I will convert it into a in teacher, uh, to see right. So, for example, if we have, for example, this 22 the 1st 2 right, we will go through and I, for example, change it. So the 1st 2 the condition will be true. We will multiply zero bytes and which is zero and we will add to Okay, then we go and check the 2nd 7 So once again, it's true. We multiply to to that we already have stored in there by 10. That means we get 20 and we add seven. So we get 27 and once again with free wi go through a multiply 27 bites and we get 270 at free, right? And yeah. So what do you want to do is then, if we reach a point when there is a some sort of character, something different and a number we would like to add detent um the damp to the total. Right. So we would have something like a total in here which would be equal to zero. And then inside here, we would have total plus equal right, because we are doing some off those right? So plus equal the attempt, if you would need, like, multiply does you would put a multiplying sign in here, right? And then we also need to set the attempt to zero rights and would be equal to zero. Um, because we said the attempt to zero, we don't necessarily have to check. Ah, what is the value of temp? Because with each other character, we would just add zero to D total. And if we add zero, nothing happens. Right? Nothing changes. So this would work totally fine. So if I just then a return d total right, uh, and run this. I think that we should get the proper results. So if I just change this to 22 and run this on the strength So if I just Brent out D count of numbers, Um, in this drink. Ah, and run this file. So if I run this ah, we get the door is a 25. All right, So why is that? Yeah, yeah, important thing. Ah, once again, when you forgot about something at the end, we also need to add detail to total right. So inside here, when we break out of this off this loop. We need to add the attempt because in here, as you can see, we get the four as a last character, Right? Bad. We are adding only ones. There is something that is not a number, right? But we should also add if there is something that is a like If we end with a number, we should also add this number, right? But it doesn't happen this way because we are adding it in the else branch right here. And it doesn't occur. So we also need to add ah, the tempt to the total. And would this change if, for example, we would have those strings eso those characters at the end? Um, well, the else branch would take place, right? But we would send then set, set d tempt to zero. So that means when we add de tempt to the total in here, we would just add zero. So no effect. So currently I think that this should work. So if I run this again, we get 29. So, yeah, there's a important thing to keep in mind when you are looking for for some string or something like dad and Ah, And you, for example, chick, if there is a something else and then you just add up something. Ah, you also need to think about whether this would work. If the number would be the last right. In this case, the number would be the last character. Right? So keep this in mind when you are going at the interview and when you are solving the actual problem. And so that's very much it for this lecture. If you have any questions, feel free to ask, and I'll see you next time. 18. 16 Wave from array: Hey, guys. And welcome to this lecture. In this lecture, we will talk about the wave or a problem. So, um, what it means well, on an input. We have some sort of list on this list is contained containing a number, and we know numbers. And we know that those numbers are sorted. So something like this, this is a possible input. And, um, what do we want to do is return a sort of wave off this array. So what is Wave wave goes up and down right up and down and up and down. And in here, you have the mathematics way of saying that. So the first element is greater or equal to the second element. And the second element is smaller than equal to the third element. And then once again, so on, And so far. So you go from you go from greater down, okay? And didn't go for adapting from down up, okay. And then once again, from up, down and from down up. Um, so the result of desk should be something like to one, um, to one, um, four free, um, six and five. Okay, so this should be the actual output off dysfunction. And if you go through those rules, you will see that it is true. So is the first element greater than the 2nd 1? Yes, it is. Is the 2nd 1 smaller than the 3rd 1? Yes, it is. Is the 3rd 1 greater than the 4th 1? Yes, it is. And is the 4th 1 smaller than the 51 year citizen is the 5th 1 Small Andy. Ah, greater attendee. 61 Yes, it is. So it is sort of a wave, if you will. And yes. So that's what we will actually create in this lecture. So, first of all, what I would like to say if you get some sort of a problem like this at a interview, you would like to ask the interviewer, maybe for some details. Maybe you can even use this use case. So, for example, rights right down some use case and then say this is the proper output and ask him. And so yeah, this is great for or question. And just make sure that you understand the problem properly. And once you understand the problem properly, you can solve it. So, um, just call this function make waves and from a list, OK, And right now, uh, what are you going to do? Well, as you can see from this use case, um, pretty much everything that we have to do in order for this to actually work is to go through each and every pair. Okay, so each and every pair ride. So, first of all, we take these two. Then we take these two, and then we take these two and we swabbed him. Right? So we basically scrubbed Oh soo. And we get this one. Yeah. OK, then we take these to swap them, and we got this thing. Okay? We took the Sioux, swap them and get the sting. It basically that is how you can actually create the, um this outcome sequence. In my opinion, this is a huge part off actually solving the problem, basically realizing what is going on and how you can actually approach it. Then if you just write a code that it's the in my opinion, simpler part, the harder part is to actually understanding problem and figure out what is going on and how you can actually solve it. So another tip that I got for you is that you can sometimes when you, for example, have, uh you can, for example, imagine a smaller input, right? And see what the solution for them might be. Right. And this should be, like, two and one and didn't say OK, so And what happens if I have one too and free, right? And then gradually increase the input and basically figure out what is actually going on. Right? So if I If I have this input, what is the output? Well, to one and free, right? Why is that? Well, because the second element needs to be smaller than the 3rd 1 Right? So Ah, what do we want to actually, right now? Let's let's basically make the gold work. So what are we going to do? Well, we want to go for each and every index in the range. Um, that would be the starting point. Would be zero. The ending point would be the length off. L um, but this is only in case l is actually. Well, I need to think about it for a second. So this one have length off free, right? And this one have length off to So, um This would mean that if we go and each and every reiteration we need to jump by two, right, we need to increment I by two. Because we need to take bears right, despair and then despair and then despair. So bear is basically I and I've us What? Okay, so I'll just write it down in here. So bear is basically I and I plus one. Okay. Um, yes. So that would mean that if the length is even, we should get ah, this to actually work, right? Because we would get zero. And then when we jumped by two. Ah, we would reach the end, right? And what if the length is free? Well, den, um, then where you would actually get, um, we would actually go through to its orations, right, Because the range would return an array containing, like, zero and two. So I would be zero in the first situation, and then I would be too. And that would be a huge problem. Because, for example, our code wouldn't work because the pair of would be different. So can we actually solve this by just adding minus one in here? No. Let's see. Um, so I think that this is actually works. So if we have to in here. So if the length is to we will get one. So it would still work for every even even number, right? If we would have length off four, we would get zero ensue, Right? Because the length would be four minus one. That's that's free. Right? Um, so this would actually work. Okay. And would it work for the ought case? Well, if the length is free, we'll get free minus one, which is two. And that would mean that the that would be with it Right on, Lee. Why? Dis list, Right? So I would be equal only to zero. And dead means it would work, even for the odd numbers. So this is actually the way to go on now we have to do is just a swab de pair. So, um yes. So let's just want them so you can do it first of all, like this, So tempt would be equal to D. L on index I and then l on index I would be equal to l on index I plus one and then l on Index I plus one would be equal to D temp like this. So this is the basic way you can. Actually Ah, you can actually solve these up. But in Python, you can also do it a bit differently. Um, in here, or I will just will just make sure that it actually works. And, um yeah, and and then I will show you how you can do it better. So, yes. So let's just define it some sort of less than here on this would be like 12345 Let's make it 12345 And then we want to make it wave, and then let's printed out. So bring D list and let's run this. Ah, run this file. Um, when we run this, we can see that we get to one for free and five, so it actually works, and it actually works quite well. So if I, for example, at the, uh, six, so did we get a even number? It works even for this case. Okay, so it works just fine, but I want to improve these solutions so that it looks like more of a siphon way to do it, if you will. Um This is basically how we can do it in other programming languages. And yet that is differently. Plausible. It's it's not like mistake to do it, but they will see that, um, you are not as comfortable in by thin. And so it's always better way to do it like this. If you if you are just swapping something, um, this is the way to actually do it. So you are basically assigning to dose to values whatever is in here, Okay. And, um, basically, this side will be will be evaluated when computer comes to this line, decide will be evaluated, and we will figure out the value off this. And then very off this, this will be stored somewhere in cash, probably. And and then what computer does is then he overrides those two values. OK, so it actually works, and you don't necessarily have to have the temp variable. So if I run this file again, as you can see, we get the exact same outfit. Um and yeah, we basically created a solution for this problem on only on two lines. Um, if you would like to make it so that we don't mutate this this list. You probably know how to do it, right. We would just create a new list and assigned those values to the new list. Right? It's nothing hard to do. So, um yes. So that's pretty much it for this for this problem. If you have any questions, feel free to ask, and I will see you next time. 19. 17 The Max sub array: Okay, guys, welcome to this lecture and his lecture. We will talk about the max Up array. So what election means? Well, as an input. Ah, we have some sort of array. It can be whatever in here. And we got some basically parts of your A. Okay, Endo Spartz are defined by those negative numbers, so every negative number basically splits the array, right? So Ah, this basically means one free ends too. And this is one separate. And the 2nd 1 is foreign five. OK, and what do we want to do? Well, we would like to find out. Basically, what's up? Array is have the greatest value. So if we sum up all the elements in the separate Ah, which one has the biggest valley? Um, so what? This would mean, actually the this one, right? This one has the biggest value because that's nine. And this one is only six, right? And so we would like to return the actual index off this. So I think that this one IHS Ah, 01234 four and five. Ok, so we would like to bring four and five as a result. So, um, like this all right. All right. Wow, it doesn't work. So, like this? Um, yes. So let's get action into it. So first of all, you can always when you get some sort of problem in an interview, can always think about some sort of each case is right for the problem that you actually get. So, um, what do you teach case in this example? Might be, um, while Etch case might be a empty rate, if that's, like correct input. Um, then you should maybe bring something like minus one. Um, then another. Each case might be a radio disc containing only negative numbers. Right. So, um, what then when? Then you should probably bring minus one or something like that. Um and then what else? Um, for example, another edge case might be a number that is array. That is containing Onley one number. OK, eso this should actually print out zero and zero. Right? Because this is the interval. Where we have this is the biggest separate on, then another. Each case might be if we have something like negative number and then the positive number, and it should bring basically one and one right, because this one is the biggest separate. Um, so, yeah, you always want to think about dose problems and no, What do you want to do now? Well, now you need to think about how you actually approach this problem. So Ah, every time you don't know how to actually solve a thing, you just break it down. So break it down into smaller problems that you can easily solve. All right, Um, So what would be the smallest problem in here? Well, ah, we need to get from this to disappoint, right? So we need to basically split up the, um, disarray, um, on intervals. Right where this negative numbers. So we need to get from this point to this point how you can do it. Well, easy. Right. So let's just define he the function. So, Max, up Ray or sub list, whatever. We get the list. And ah, what are we going to do? Well, for every value in the list, um, we can either, for example, keep track off a off those intervals. So, um so, for example, we can have, like, basically this thing. Keep in mind, this basically handled this thing and then some up all of those elements and figure out which one is the biggest about. We would need those index. It's right on. Do so in the end. We also need to keep in mind that we need to have dose indexes and and yes. So what will be a better way to do it is to actually maybe store, um de biggest central, right? And only keep track, basically figure out. OK, which one is the biggest interval? And then, uh, we can check with the other intervals. Weather Day are bigger or not. So, um, let's just define a starting index. So index start, which will be equal to zero and then index end, which would be once again equal to zero. And then we would get a some, um some off sub list or subway, right? And it would be the total sum off that part. Okay. And then what we can do is actually just anouma rates delist so that we go through ah, index and values, right. And, um, what we can do Well, if the if d value is negative. So that means smaller den zero. Uh, what do we want to do? Well, that means there is a new interval. Right? So, um, the new interval, Uh, that means we need to, um, create a keep somehow track off the new interval, so Ah, let's just create a new variable called New in Terrible Start. All right? And this would basically because we need to keep track off the best one, right? And then we need to keep track of the new one. In case the new one is better. We need to swap it with the best one. Okay, I have to make sense. So if the value is smaller than zero, that means we get to this born right. Something is negative. We know that we need to start in new interval, right? And the start of the new interval would be at the index bus. Wanna. Right. So that means this thing, Okay. And, um yeah, and we also need to close the previous one. Right? So figure out the some off the previous one. Okay, So, um, so this would be actually at the end. We first need to figure out the some of the previous one because the previous one is actually stored in this thing. Right. Um So what rallies? We actually have. Well, we have these some off separate. So that's the some off the best one. Right? So that would mean, for example, in this case, this would be, uh, six. Right? And then we have those indexes we don't need to take. We don't need to care about them right now. Um, yes. So, um, what do we want to do now? We want to actually figure out whether the new interval have a bigger value than the old one. And in order to do dad. Ah, we need to also define the some off off new interval or new separate. Okay. Uh, so let's also change this. Think two new separate so that we call it the same way. So new separate start and then some over news off. New separate, which would be zero by when we are starting. Right. Okay. So, um, so we need Teoh actually. Check if the some of the new separate right, if the some of the new separate eggs greater than the sum off the previous separate right? So the if he some off the off separate, it's actually smaller, right? Use only these things in conditions. Dendy some of the new one. If it s, we would like to swab dose, right. So swap, uh, the separates. So it's up, Ray in Texas. Um, why, Why We want to swap those? Well, because we figure out that these new this new interval have actually greater value than greater something disprove this one, right? Eso we said the index off index start, that would be to the new interval start. Right. And, uh, or sorry, new substance operates. Start. Okay. We need to change those things. And then we need to also change d sub array. Right? So so d some would be equal to this thing. All right. We need to also said this thing to zero because we will use it later on 40. Next interval, right? And, ah, what do we want to do next? Um ah. We also need to define the index of the of the end. Right. So the index off the end and which one is it? Which one? What? What would be the end? So, for example, And let's say this case, uh, we have reached the negative number, right? This is the of condition. If there is a negative number, so we want to basically take the summer off the interval that we got This is the starting point, right? The one is the starting point. And what is the ending point? While the ending point iss at index off distinct minus one. Right. So basically the index that we are a trading and minus one. So this would basically define the d separate, and this would basically take care of the actual some. Okay. And then we basically start being new, New separate, right? And it also, if the value is not negative, what do you want to do? Well, um, we want to just add the number to the some of the new separate, so this would be plus equal devalue, right? And that is just about it. Uh huh. So, basically, if the number is positive, we are just adding it up, okay? And if we get to a negative number, we basically closed the interrupt and figure out whether it is the greatest one that we already that we have. Okay, so in the beginning, the some off summary is equal to zero. So if there is something that is greater, for example, with this too, Okay? um, we would get a some of the new separate equal to two, right? And yes. So it would actually work for this? Um, yes. Oh, So another thing that we also need to do is Eddie end in here after this for loop. Ah. We also need to keep in mind that we can end without the negative number. Right? Eso dead mean that we need to check this thing. Right? So this thing needs to be also in here. So after we go for the lube, um, we need to check whether the last interval that we have in the array, um, it is actually greater than the best one that we already got. Um, And if it is, we need to scrub those two values and basically, because we really don't need, um because we really don't need while we don't have the index in here. So inside here should be just the ah, the length off the off the list. Right? Because this is the last index in the array, and yet So, um, okay. And yeah, because we need to even kind of close the last last in server. Right? And we are closing it with each negative value. Okay, so we need to just keep this in mind. And, um yeah, okay. And I'm when I'm not sure what I'm forgetting about something. I would also we also need to take care of those off those etch cases. But let's for now, let's just assume that we will have only does kind of normal cases and eso Let's just bring this. And then we will take care of those each bases, right? Because I'm pretty sure it won't work for everything currently. So yeah, let's just call it so makes up array. You are Sorry, Max. Separate off something similar. Something like 12 then minus one and then 45 So 45 would be the biggest separate. So let's actually run this thing and see OK, so we get free And four, which means 012 free, which is for and for, which is five. So yeah, it actually works on the normal case. Um, so what? It actually worked on those off those on those etch cases that we defined? Well, it wouldn't certainly work on this one, because that's ah, minus one. Right. Um, so this one should return minus one. And this one should also return minus one s. So what happens if the array is empty? How do we know that you're a is empty? Well, we know that basically the some off the sub array stays zero. Right? If these some of these separate state zero, um, we know that these apparatus this empty right, So inside here, we just need to check if these some of the separate right, if the some of these separate. So that means if it is zero. Ah, that means we want to bring ah dee minus one. Okay. And in every other case, we would like to bring the actual results. So else we print do result. Okay. Um wow, let's see with those other cases. So, for example, with the to, um, when we get to, we will basically go through, uh, the loop. We will. Said these some of the new separated too. Okay, um, the index start will be zero. And then inside here, we would set it to zero. So this would actually work for the two. If you Yeah, it's always good thing when you are at the interview. If you just go for the coat and figure out whether it actually works for those etch cases. And I think that the interviewer would really love to see something like this in the interview. And you can really talk through Ah, howdy computer with evaluate the code. That is a great thing to do. OK. Ah, Then the last one last use case, I think this should also work. So ah, let me actually try it out and see whether it actually works. So that's just bump it in there and randy file. So it returns one and one, which is correct. Dent if we but was there just to it should return zero and zero and the dust. And then if we just post those negative numbers so something like this, let's see if we run this, it returns zero and zero. So Dad is actually that is actually wrong. So the algorithm doesn't work for does negative inputs. And why is that? So let's let's go for two killed ones again. Um, what happens so inside here, this is always true. So we never get to this else brain. Okay, because all of those numbers are negative. Uh, those are both zero So we get, uh, this will never happen. So we are just setting the new separate. Okay, then we jump out. Uh, this will once again never execute because this is false, okay? And we get to disappoint and summer. Ok, I see it. All right, so this should be check if the sum is equal to zero, actually, and if we're under CIA, it actually works right now. So it's also tried out on those different. Each case is so with the zoo, it actually didn't work. OK, so yeah, also, I we need to set. Um, yeah, and this in this case, we need to set it because we are then checking, checking, devalue. Right. And basically, if there is the only there's only interval right. With no negative numbers, we would get to this point. And we need to set this thing Teoh so that we don't jump into this condition. Right? So if I run this thing again at the return zero and zero, so yeah, now it's ah, working properly. Um, this is the, in my opinion, these simplest way to do it. Ah, with the time complexity, uh, orphan, there is no better way to do this than over fen? Um, yeah. So that's pretty much it for this video. If you have any questions, feel free to ask, and I'll see you next time.