And welcome back.
So in this video, let us continue our discussion and solve the last variation of this problem, which
is returning the answer as a new list.
So let us now try to first intuitively understand this problem again.
So pretty sure that the example which I am giving with respect to teachers is clear.
So in this we have to actually return a list as an answer.
But few things to note in this particular variation is that a we are not passing any list into the function
definition.
We are not passing any list into the function definition, and b that there is no global list as such
as well, right?
So in this we are actually have the task of creating this particular list.
So let me just define the function.
Return all indices as a list.
We will be getting all our numbers.
We will be getting the X, which we need to find, and the index.
And this time, actually we have to return our answer list.
So when we will be calling this particular function, we actually will be returning our list.
Right.
So let me just copy this example as it is great.
Again before starting with the solution, we should know that what the answer should be.
We should try to write up a test case and actually check the same, either in the context or through
our interviewer.
The answer for this particular use case will of course be one, three and five, right?
So this is what we should return.
Now first understand that let us first understand the intuition and then we are going to move forward.
Uh, see now pay attention everyone.
Again I will explain you using the same example this time.
Again, there is still a teacher.
There is again a teacher, right?
But this time the teacher has actually not given you anything.
And teacher is in a way asking you that.
Hey, you go and please bring me on a paper.
Okay.
Or let's say on a diary or something.
Bring me a diary.
Okay.
So that is something which we are returning.
Right now, we are actually the one who are giving the diary to the teacher.
We are the one who is giving this diary to the teacher.
So teacher is saying that.
Hey, give me a diary in which names of all the defaulters are written.
Right.
So let us say these are all my students.
And again, we have to understand one thing here as well.
Pay attention everyone.
This time I am not able to pass this diary, right?
This is not something which is allowed.
Because if that would have been the case, then I would have passed the teacher's diary.
Only this time I actually have to ask this particular person.
Because this is my first person, right?
That, hey, give me the names.
Give me the names of all the students who have not done their homework.
Right.
So let us see what the thought process of this person will be.
Okay.
And let us solve this with respect to recursion.
The very first is going to be of course, the base case.
Now again, if the class is empty, if the class is empty, then we are just going to return an empty
string, right?
We are not doing.
We cannot actually have any defaulters.
We cannot.
We will not be finding the element in our particular this question.
So let me write down the base case.
If length of my L one right equal equal index I am just going to return empty list.
This time I am returning the empty list.
Okay, not just returning without anything, I am just returning the empty list again.
I've used this length of L one equal equal index because that is how we are checking it.
If the index will be zero and length will be zero, then we are going to match and I am going to return
my answer.
Okay, so I hope this thing is clear everyone.
So this is going to be my base case.
Now let us see what's going to happen once we move forward.
And this is something where I want you to pay attention.
When I ask this particular person, when I asked this particular person that, hey, give me all the
list of people who have not done their homework.
Now, if you think in terms of recursion, what exactly is going to happen?
This person is going to call to all these people, all these students and say that, hey, you give
me all the list of students who have not done their homework, and I will just basically add my name
in the starting or in the end, that should not.
That is something which we will discuss afterwards, but in recursion.
Since starting, I have been telling you that we have to visualize our problem by making it small.
So the small problem actually kind of gets written in this way that, hey, you just give me the same
list and I will see what I have to do after that.
Right?
That is something which we are going to do.
So maybe what I can call or what I can ask is small list.
Okay, just let me do this.
Return this function L1X and index plus one.
Now I do not need to actually question.
I do not need to actually question how this thing is going to roll out.
Right?
I do not need to question this.
That is what recursion tells us.
That is what I have been pushing you that Assume that.
Okay, now you got the answer.
Now let us see what exactly we will be doing.
Okay.
So let us go back into our example.
I'm going to check if I have done the homework or not.
Okay.
So from here, once I call for this particular function, once I call for this this people.
So this is all students.
I will be getting a list or getting a basically paper or let us say a diary.
Let us keep it paper only.
I will be getting a paper where all the defaulters name will be written.
Now it is on me, okay, it is on me.
If I want to add list, add my name on the top or I want to add my name on the bottom.
Again, I can create a very new list as well.
That is totally on me as well.
I can create a new list, right?
So now what's going to happen?
Pay attention everyone!
I have gotten a list, okay?
What I am doing is my answer list, the one which I am going to return.
Okay.
It's going to be.
If so, first I have to check.
Okay.
If L one of index is equals to x, then of course I have to add something in my answer list, so we
will see how we can do that.
Else, I think we should be very much more than happy to just return an answer list, right?
So and let me keep it outside, not in else because I can just return it.
No changes will be there if this is not true.
And anyway, I have to return this answer list, right?
So now pay attention everyone, what is going to happen?
And I have to make sure that I'm able to define the.
Okay, so one more thing, which I want all of you to understand is that if this is not the case, then
I should return the smallest.
Then I should return the smallest.
And here I should be defining my answer list.
Right?
So if I have actually find C pay attention then what I want you to explain here is that if I have actually
not if I have done my homework, then I don't need to change anything.
I can return this list as it is.
That is what I'm doing.
So if it is not equal to if it is equal to x, then I need to make some changes.
Else I should be good to return this right, else I am very much good to return this.
Okay, so now pay attention.
What's going to happen now pay attention.
So either either so I can just append my index in this list.
But this time I'm adding my name towards the end.
This is what I am doing.
And I can return my small list.
Right.
And we don't need to write this.
Actually, we don't need to write this.
This particular case will handle it altogether till now.
I hope you all are comfortable with this particular thing.
So when this will happen, I will get my result as five, three and one.
Okay?
Why will this be the case?
Let me quickly run it for you because I want you to first run and tell.
And this time let me explain you using my I would say the way we should write.
Okay.
And instead of having the Python tutor.
Because that is something which we should also see, though I have been doing it for the initial questions.
But now let me try this for this question as well.
And I'm just going to assume till this fourth elements.
Okay.
So see I am passing 3252 okay.
That's the very first function call which I make here.
And I'm assuming that this is going to return me a list, which is going to be my answer list.
Okay.
First I check for the base case which is a false note.
Right?
Then I call for the next function.
Now again I was let me just use the index one as in blue color.
I was pointing here.
Okay.
Now if I make it again this is 3252.
But this time I am pointing here okay.
Again, once I go forward.
It is three, 252.
This time I am pointing here 3252.
So this is the kind of analysis and I would say drawing, which I want all of you to make whenever you
are solving the questions and at least for the first 15, 20 questions, if you make it, believe me,
there will be no recursion question which you cannot do no matter how hard it is, because this is what
most students skip on, and then they face a lot of problems.
And this is something which even by doing this, I was able to do it like I was able to master recursion.
If you are not doing this at your end, you will have a very hard time understanding recursion no matter
from where you study, because recursion is actually something where, like I told you in the very starting
as well, that this was the major case where I faced the most problem, this assuming part.
But once you draw this diagram right, once you draw these three diagrams and everything, you will
be able to actually understand the same thing.
Okay.
So actually just let me draw this using yellow because it is more visible.
So this is my index right.
And finally when I make the last call.
Of course it is outside.
So it does not matter.
And the base case is reached.
Now pay attention everyone.
What exactly are we going to return?
I am drawing it by a green, so it is going to be an empty list, right?
It is going to be an empty list which I am going to return.
Now, once this particular instance has gotten an empty, it is going to check if L1 index is equal
to x.
This time it is because we are taking x as two.
So in this particular empty list it is going to add three.
Third is the index.
Now this three will be going to return right.
This is what I am returning I am returning my small list okay.
Now when I get this particular three I am going to check if this is equal to two.
This is not so I am going to return my list as it is.
Now is where some thing will happen.
See when I am trying to append.
Now when I say that okay, is this equal to two?
Yes, this is equal to two.
But now I am doing append.
So now when I am appending this will be appended towards the end.
This will be appended towards the end.
That's the reason I will be getting.
I was saying that I will be getting this as 351 and not 135.
I'm going to return again.
This is not equal to two.
So I'm going to finally return the major answer which is three one okay.
So this is how the whole tree will go.
Again if you understand, if you are able to somehow add in the starting.
If instead of appending, you are able to add in the starting.
Okay, we have a insert function, right?
We have a dot insert function where I can provide the index and the what I want to add.
Right.
Then this whole will be equal to one, three, five or in this particular case one three.
Because now in this particular step when I will get this particular list, I will be appending in the
starting instead.
Okay.
So this is just a little bit thing which you have to take care when you are changing your list.
And I think this particular example should help you explain, because when you make sure that your problem
is getting smaller and you are getting a list, you are not just working on that list, so you do not
worry on that.
Okay, so on that note, let me just run this now.
Okay.
I have to print the list as well.
531 right.
As we saw.
531.
This fix is pretty easy if you just do insert.
Okay.
And let us say insert.
One second.
Yeah.
Insert it is index and object.
Right.
So index is going to be zero always.
And object is my basically in this particular use case index object is the index because that is what
we are adding.
And if you run it now you get the answer as 135.
Now again you will see that how easy things are.
If you are able to understand the intricate details.
And that is what I want you, all of you, to focus on.
And that will become clear once you draw these trees.
Okay, cool everyone with that.
Actually, we have completed all the variations.
Please make sure that you remember this with all these intuitive example as well as industrial example
of Amazon Flipkart which I am giving.
These are the kind of questions which are asked in major product based companies.
So please make sure that you are able to understand them.
And then I would say do some practice on that.
I will be providing you some questions and in the next class.
Now we are going to start with some sorting algorithms which are based on recursion.
Okay, so cool then thanks a lot everyone.