Hello everyone and welcome back.
In this section we are taking a look at an interesting question, a famous question which is called
kth symbol in grammar.
So let's dive right in.
Let's take a look at the question.
We build a table of n rows one indexed.
We start by writing zero in the first row.
Now in every subsequent row, we look at the previous row and replace each occurrence of zero with zero
one, and each occurrence of one with one zero.
For example, for n is equal to three, the first row is zero, the second row is zero one, and the
third row is 0110.
Given two integers n and k, return the kth symbol and its one indexed in the nth row of a table of
n rows.
So this is the question.
Now let's try to understand this question and get a good intuition of what is asked of us.
So over here it says that in the first row we will just write zero.
And in each subsequent row we will replace a zero with zero one and an occurrence of one with one zero
in the previous row.
All right.
So let's take a look at how that looks like.
So first we write zero.
Now in the next row we are going to replace this zero over here with zero one.
So that is what's given over here.
So let's write zero one over here.
Now in the next row for this zero over here, we'll write zero one.
And for this one over here we'll write one zero.
So this would be the third row.
And it goes on in this manner.
So this is n is equal to one.
This is n is equal to two.
And this is n is equal to three.
Now let's say n is given as three.
And if k is one then we would have to return this value over here which is zero.
Similarly, if k is equal to two we would have to return this value.
And if k is equal to three we would have to return this value.
And if k is equal to four we would have to return this value.
So this is the question.
So we will be given n and k.
So two integers n and k would be given to us.
Based on this we would be able to form the values for the nth row as we have done over here.
And then for that nth row we would have to pinpoint the value at the kth index.
And notice that k is one indexed okay.
So this over here is index one as per the question.
And then we would have to just return the value at that particular index.
So this is the question at hand.
So I'm sure we have developed a good understanding of the question.
So we have 001 and then the next would be zero one, one zero, etc..
And then we just need to go through this and identify the value at the kth index.
Now remember in coding interview questions it's always very important to ask clarifying questions before
you go ahead and solve the question.
So this is very important.
And intentionally you will see that in many coding interview questions, complete details won't be given
to you.
Now, what are some of the clarifying questions that you could ask for this particular question at hand?
One possible question is is it possible that n is given as zero?
Okay.
So because over here it says that this is the first row.
Now what if n is equal to zero?
Now let's say the interviewer replies that no n will definitely be greater than equal to one.
All right.
Now what would be another question that could come into your mind again?
Another question could be what if K is out of bound because node is over here.
When n is equal to three, there are only four possible values of k.
What if for n is equal to three?
K is given as five.
Now is that even possible?
So that could be a very valid question.
Now let's say the interviewer replies that this will not happen.
So let's say the interviewer says that.
For n for a particular value of n, the value of k will be between 1 and 2 to the power n minus one.
So that means again we know that it's 0010110.
Let's say n is equal to three.
So if we put three over here.
This would be two to the power, three minus one, which is two.
So this would be four.
So that indicates that k would be between 1 and 4.
And we know that for each of these values of k we have a value to return.
So there would not be a case where k is out of bound.
All right.
So we have got a good idea of the question what is asked of us.
And we have got our questions clarified.
Now is the time to go ahead and write a few test cases.
Remember these are just combinations of input and the expected output for that particular input.
And always in interview coding interviews.
Remember you can form these test cases together with the interviewer to ensure that both of you are
at the at the same level or you're in agreement.
Now let's take a look at the question and write a few test cases.
So I've just written out over here the scenario where n is equal to four.
So this is n is equal to one.
This is n is equal to two.
This is n is equal to three.
And this is n is equal to four.
Now remember writing test cases in many questions is particularly helpful because it will give you some
time to think about the problem at hand.
And you will start building an intuition about the approach that you could take to solve the question.
So again writing test cases is very helpful.
Now over here, if we have this, it's very clear that if n is equal to one and k is equal to one,
we would have to return the value of zero, because this is the case where n is equal to one.
Now let's say n is equal to four which is this case over here.
And if k is equal to one then we would have to return zero because that's this value over here.
And if n is equal to four which is this one.
Again if k is equal to eight we would have to return one, which is what we have over here because this
is one, this is two, this is three, this is four, this is five, this is six, this is seven and
this is eight.
Now this is pretty clear to us now.
So I think this should be good enough with respect to test cases.
Now in the next video let's go ahead and start developing some observations.
And let's start to develop the intuition on how we can solve this question.