1 00:00:00,400 --> 00:00:02,800 Hello everyone and welcome back. 2 00:00:02,800 --> 00:00:08,410 In this section we are taking a look at an interesting question, a famous question which is called 3 00:00:08,410 --> 00:00:10,060 kth symbol in grammar. 4 00:00:10,060 --> 00:00:11,980 So let's dive right in. 5 00:00:11,980 --> 00:00:13,600 Let's take a look at the question. 6 00:00:13,600 --> 00:00:17,830 We build a table of n rows one indexed. 7 00:00:17,830 --> 00:00:21,010 We start by writing zero in the first row. 8 00:00:21,010 --> 00:00:29,290 Now in every subsequent row, we look at the previous row and replace each occurrence of zero with zero 9 00:00:29,290 --> 00:00:32,740 one, and each occurrence of one with one zero. 10 00:00:32,740 --> 00:00:39,190 For example, for n is equal to three, the first row is zero, the second row is zero one, and the 11 00:00:39,190 --> 00:00:41,500 third row is 0110. 12 00:00:41,560 --> 00:00:51,100 Given two integers n and k, return the kth symbol and its one indexed in the nth row of a table of 13 00:00:51,100 --> 00:00:51,820 n rows. 14 00:00:51,820 --> 00:00:53,170 So this is the question. 15 00:00:53,170 --> 00:00:59,650 Now let's try to understand this question and get a good intuition of what is asked of us. 16 00:00:59,650 --> 00:01:04,570 So over here it says that in the first row we will just write zero. 17 00:01:04,570 --> 00:01:12,040 And in each subsequent row we will replace a zero with zero one and an occurrence of one with one zero 18 00:01:12,040 --> 00:01:12,820 in the previous row. 19 00:01:12,820 --> 00:01:13,180 All right. 20 00:01:13,180 --> 00:01:15,040 So let's take a look at how that looks like. 21 00:01:15,040 --> 00:01:17,080 So first we write zero. 22 00:01:17,230 --> 00:01:22,540 Now in the next row we are going to replace this zero over here with zero one. 23 00:01:22,540 --> 00:01:24,070 So that is what's given over here. 24 00:01:24,070 --> 00:01:26,260 So let's write zero one over here. 25 00:01:27,120 --> 00:01:33,420 Now in the next row for this zero over here, we'll write zero one. 26 00:01:33,420 --> 00:01:37,290 And for this one over here we'll write one zero. 27 00:01:37,290 --> 00:01:38,880 So this would be the third row. 28 00:01:38,880 --> 00:01:41,460 And it goes on in this manner. 29 00:01:41,460 --> 00:01:43,170 So this is n is equal to one. 30 00:01:43,170 --> 00:01:44,700 This is n is equal to two. 31 00:01:44,700 --> 00:01:46,710 And this is n is equal to three. 32 00:01:46,740 --> 00:01:49,440 Now let's say n is given as three. 33 00:01:49,440 --> 00:01:55,530 And if k is one then we would have to return this value over here which is zero. 34 00:01:55,530 --> 00:02:00,240 Similarly, if k is equal to two we would have to return this value. 35 00:02:00,240 --> 00:02:03,630 And if k is equal to three we would have to return this value. 36 00:02:03,630 --> 00:02:07,410 And if k is equal to four we would have to return this value. 37 00:02:07,410 --> 00:02:09,030 So this is the question. 38 00:02:09,030 --> 00:02:11,790 So we will be given n and k. 39 00:02:11,790 --> 00:02:14,790 So two integers n and k would be given to us. 40 00:02:14,790 --> 00:02:21,090 Based on this we would be able to form the values for the nth row as we have done over here. 41 00:02:21,090 --> 00:02:27,420 And then for that nth row we would have to pinpoint the value at the kth index. 42 00:02:27,420 --> 00:02:30,840 And notice that k is one indexed okay. 43 00:02:30,840 --> 00:02:34,410 So this over here is index one as per the question. 44 00:02:34,410 --> 00:02:38,880 And then we would have to just return the value at that particular index. 45 00:02:38,880 --> 00:02:40,740 So this is the question at hand. 46 00:02:41,350 --> 00:02:45,280 So I'm sure we have developed a good understanding of the question. 47 00:02:45,280 --> 00:02:50,230 So we have 001 and then the next would be zero one, one zero, etc.. 48 00:02:50,230 --> 00:02:55,810 And then we just need to go through this and identify the value at the kth index. 49 00:02:55,810 --> 00:03:04,360 Now remember in coding interview questions it's always very important to ask clarifying questions before 50 00:03:04,360 --> 00:03:06,550 you go ahead and solve the question. 51 00:03:06,550 --> 00:03:08,080 So this is very important. 52 00:03:08,080 --> 00:03:14,080 And intentionally you will see that in many coding interview questions, complete details won't be given 53 00:03:14,080 --> 00:03:14,620 to you. 54 00:03:14,620 --> 00:03:21,400 Now, what are some of the clarifying questions that you could ask for this particular question at hand? 55 00:03:21,400 --> 00:03:26,950 One possible question is is it possible that n is given as zero? 56 00:03:26,950 --> 00:03:27,340 Okay. 57 00:03:27,340 --> 00:03:30,040 So because over here it says that this is the first row. 58 00:03:30,040 --> 00:03:31,930 Now what if n is equal to zero? 59 00:03:31,930 --> 00:03:39,100 Now let's say the interviewer replies that no n will definitely be greater than equal to one. 60 00:03:39,370 --> 00:03:40,180 All right. 61 00:03:40,180 --> 00:03:45,340 Now what would be another question that could come into your mind again? 62 00:03:45,340 --> 00:03:50,710 Another question could be what if K is out of bound because node is over here. 63 00:03:50,710 --> 00:03:54,850 When n is equal to three, there are only four possible values of k. 64 00:03:54,850 --> 00:03:57,250 What if for n is equal to three? 65 00:03:57,250 --> 00:03:58,690 K is given as five. 66 00:03:58,690 --> 00:04:00,130 Now is that even possible? 67 00:04:00,130 --> 00:04:02,350 So that could be a very valid question. 68 00:04:02,350 --> 00:04:06,970 Now let's say the interviewer replies that this will not happen. 69 00:04:06,970 --> 00:04:10,270 So let's say the interviewer says that. 70 00:04:10,870 --> 00:04:18,580 For n for a particular value of n, the value of k will be between 1 and 2 to the power n minus one. 71 00:04:18,580 --> 00:04:23,380 So that means again we know that it's 0010110. 72 00:04:23,380 --> 00:04:25,120 Let's say n is equal to three. 73 00:04:25,120 --> 00:04:27,070 So if we put three over here. 74 00:04:27,740 --> 00:04:31,490 This would be two to the power, three minus one, which is two. 75 00:04:31,520 --> 00:04:33,050 So this would be four. 76 00:04:33,470 --> 00:04:37,460 So that indicates that k would be between 1 and 4. 77 00:04:37,460 --> 00:04:42,320 And we know that for each of these values of k we have a value to return. 78 00:04:42,320 --> 00:04:45,950 So there would not be a case where k is out of bound. 79 00:04:46,550 --> 00:04:47,180 All right. 80 00:04:47,180 --> 00:04:52,010 So we have got a good idea of the question what is asked of us. 81 00:04:52,010 --> 00:04:55,700 And we have got our questions clarified. 82 00:04:55,730 --> 00:05:01,010 Now is the time to go ahead and write a few test cases. 83 00:05:01,100 --> 00:05:08,000 Remember these are just combinations of input and the expected output for that particular input. 84 00:05:08,000 --> 00:05:11,180 And always in interview coding interviews. 85 00:05:11,180 --> 00:05:19,310 Remember you can form these test cases together with the interviewer to ensure that both of you are 86 00:05:19,310 --> 00:05:22,850 at the at the same level or you're in agreement. 87 00:05:22,880 --> 00:05:27,770 Now let's take a look at the question and write a few test cases. 88 00:05:28,250 --> 00:05:33,560 So I've just written out over here the scenario where n is equal to four. 89 00:05:33,560 --> 00:05:35,000 So this is n is equal to one. 90 00:05:35,000 --> 00:05:36,590 This is n is equal to two. 91 00:05:36,590 --> 00:05:38,150 This is n is equal to three. 92 00:05:38,150 --> 00:05:40,460 And this is n is equal to four. 93 00:05:40,610 --> 00:05:49,280 Now remember writing test cases in many questions is particularly helpful because it will give you some 94 00:05:49,280 --> 00:05:52,160 time to think about the problem at hand. 95 00:05:52,160 --> 00:05:57,920 And you will start building an intuition about the approach that you could take to solve the question. 96 00:05:57,920 --> 00:06:01,010 So again writing test cases is very helpful. 97 00:06:01,040 --> 00:06:08,390 Now over here, if we have this, it's very clear that if n is equal to one and k is equal to one, 98 00:06:08,390 --> 00:06:14,120 we would have to return the value of zero, because this is the case where n is equal to one. 99 00:06:14,150 --> 00:06:18,500 Now let's say n is equal to four which is this case over here. 100 00:06:18,500 --> 00:06:24,620 And if k is equal to one then we would have to return zero because that's this value over here. 101 00:06:25,220 --> 00:06:28,370 And if n is equal to four which is this one. 102 00:06:28,370 --> 00:06:35,480 Again if k is equal to eight we would have to return one, which is what we have over here because this 103 00:06:35,480 --> 00:06:41,330 is one, this is two, this is three, this is four, this is five, this is six, this is seven and 104 00:06:41,330 --> 00:06:42,350 this is eight. 105 00:06:42,470 --> 00:06:45,110 Now this is pretty clear to us now. 106 00:06:45,110 --> 00:06:49,490 So I think this should be good enough with respect to test cases. 107 00:06:49,490 --> 00:06:54,770 Now in the next video let's go ahead and start developing some observations. 108 00:06:54,770 --> 00:06:59,840 And let's start to develop the intuition on how we can solve this question.