1 00:00:00,660 --> 00:00:06,600 So when we come up with our first test case, we call it our best case test case because we want it 2 00:00:06,600 --> 00:00:13,920 to really help us derive all of the correct insights so that we can get to the correct solution in order 3 00:00:13,920 --> 00:00:18,840 for us to get all the right insights, we need to make sure we're looking at the total problem space, 4 00:00:19,110 --> 00:00:25,500 which means that anything that might sway our logic is going to be captured in this test case or at 5 00:00:25,500 --> 00:00:27,040 the very least, we're going to try. 6 00:00:27,540 --> 00:00:34,440 So when I say that, when you look at this question, your intuition tells you that the most important 7 00:00:34,440 --> 00:00:41,040 thing other than getting all of these less notes into one level, is that the order of the list notes 8 00:00:41,040 --> 00:00:43,730 that get merged together is important. 9 00:00:44,130 --> 00:00:51,390 We care about the order in which the list notes appear in one single, doubly linked list. 10 00:00:52,290 --> 00:00:58,240 When that's the case, really think what are the factors that might affect the order? 11 00:00:58,290 --> 00:01:03,930 You don't have to be certain, but it should be enough that your test case tests it because we need 12 00:01:03,930 --> 00:01:10,820 to use it to actually approach the insights that we need to know in order to come up with a solution. 13 00:01:12,240 --> 00:01:18,030 The first one that jumped to us is that multiple levels might influence this outcome. 14 00:01:19,050 --> 00:01:25,180 So, for example, we know that for sure we can have multiple levels beyond just two. 15 00:01:25,920 --> 00:01:34,920 So here, if we come up with a first doubly linked list and inside we have a child, let's say, at 16 00:01:34,920 --> 00:01:37,980 17 2:00 and this child has its own list. 18 00:01:41,330 --> 00:01:44,840 And then inside of this child, this child has its own list. 19 00:01:48,510 --> 00:01:54,210 We have three levels, so here when we actually start stepping through it and trying to figure out the 20 00:01:54,210 --> 00:02:00,480 correct order to merge these list nodes in, we at least have three levels, which is enough for us 21 00:02:00,480 --> 00:02:07,350 to consider what happens about the order of 10 and 11 compared to seven, eight and nine when these 22 00:02:07,380 --> 00:02:09,700 all get merged into the first level. 23 00:02:10,170 --> 00:02:11,860 So that's one big thing that we can do. 24 00:02:12,600 --> 00:02:19,430 The second is, does multiple children at the same level influence the order or at the very least, 25 00:02:19,440 --> 00:02:22,290 is there a way that we can account for it so it doesn't? 26 00:02:24,770 --> 00:02:30,650 So here we can add another child right here and let's say this one is 12. 27 00:02:34,210 --> 00:02:41,200 So with this, we have multiple children at this level as well, so we know that the 12 13 must come 28 00:02:41,200 --> 00:02:43,720 between the five and the six just by looking at it. 29 00:02:44,470 --> 00:02:47,860 So at the very least, we know that here we have captured enough. 30 00:02:47,860 --> 00:02:52,440 If the 12 and 13 end up anywhere up here in the front, we know we've probably done something wrong. 31 00:02:53,680 --> 00:02:59,980 From here, we need to come up with what the final output of this linked list will look like, and here 32 00:02:59,980 --> 00:03:07,060 we can actually start thinking and getting our gears, turning about what the flow of merging might 33 00:03:07,060 --> 00:03:13,390 be, because we need to be able to do this in person before we even start thinking of a solution. 34 00:03:14,620 --> 00:03:20,860 So we know that for sure we want to merge the seven, eight and nine into the one, two, three. 35 00:03:21,920 --> 00:03:28,640 This 10 and 11 should never come before the seven, eight and nine, because this is a child of the 36 00:03:28,640 --> 00:03:31,490 eight, which is inside of the seven, eight, nine. 37 00:03:32,150 --> 00:03:37,100 So if 10 and 11 ever appears in this list before, seven, eight and nine, we know we've done something 38 00:03:37,100 --> 00:03:37,340 wrong. 39 00:03:37,850 --> 00:03:44,480 But what we can see here is that if we start going from one to two to should not attach the three because 40 00:03:44,480 --> 00:03:46,930 it has a child, we know that the seven is important. 41 00:03:47,330 --> 00:03:52,970 So here we can immediately start writing that we need one, two and then seven. 42 00:03:53,860 --> 00:03:56,910 From seven, does it have a child, it doesn't. 43 00:03:56,920 --> 00:04:00,190 So we know that we can start upending the rest, which is the eight. 44 00:04:01,740 --> 00:04:05,920 Here we can see the eight has a child, so the next value is not going to be nine. 45 00:04:05,940 --> 00:04:08,250 It's going to be the child value, which is 10. 46 00:04:10,310 --> 00:04:15,590 Then we add the 11 because we see that none of these have any children, so we can just slot this right 47 00:04:15,590 --> 00:04:16,790 between the eight and the nine. 48 00:04:17,790 --> 00:04:18,810 And then we have the nine. 49 00:04:19,820 --> 00:04:21,770 Now that we have the nine Wiecek. 50 00:04:22,920 --> 00:04:26,160 What comes after two, it's three, so now we add the three. 51 00:04:27,160 --> 00:04:33,570 Then we add the four and then we add the five, once we've added the five, we see the five as a child, 52 00:04:33,580 --> 00:04:37,120 so we can't possibly add the six from here on, we got to go down. 53 00:04:40,510 --> 00:04:41,700 12 has 13. 54 00:04:41,950 --> 00:04:48,610 None of these have any children, so we know that once 13 is in there, we can append what was originally 55 00:04:48,610 --> 00:04:50,770 at the end of five, which is six. 56 00:04:54,430 --> 00:05:01,150 And now we have our full, doubly linked list, so this is what it flattened into one level looks like. 57 00:05:02,060 --> 00:05:08,030 So now that we have this single link list and we have walked through some of these examples, we have 58 00:05:08,030 --> 00:05:10,820 a general idea of what the merger should look like. 59 00:05:11,360 --> 00:05:18,290 We know that we can merge a level in it doesn't affect the outcome as long as when we advance to the 60 00:05:18,290 --> 00:05:19,580 next list node. 61 00:05:19,760 --> 00:05:27,950 Inside of this merged in child, we account for its children and any children that the remaining list 62 00:05:27,980 --> 00:05:28,910 nodes might have. 63 00:05:29,030 --> 00:05:31,130 It will become much more apparent when we start, actually. 64 00:05:32,000 --> 00:05:39,020 But right now, just from walking through, turning our test case into the correct answer, we've already 65 00:05:39,020 --> 00:05:40,700 kind of seen what this looks like. 66 00:05:40,880 --> 00:05:43,880 Your intuition will help you do this anyways. 67 00:05:44,150 --> 00:05:49,760 But the problem is you have to slow it down and really start thinking about what these steps could mean 68 00:05:49,910 --> 00:05:55,340 and how that order might matter, because from here, it might give you hints towards getting to your 69 00:05:55,340 --> 00:05:55,820 solution. 70 00:05:56,780 --> 00:06:00,140 So what this test case, we also need to account for some null cases. 71 00:06:00,410 --> 00:06:04,250 In this case, we might just account for what happens if we get null as an answer. 72 00:06:05,390 --> 00:06:08,010 Then when this happens, we do want to return null back. 73 00:06:08,630 --> 00:06:12,230 Also, what happens if we receive a single level or a single node? 74 00:06:12,230 --> 00:06:13,690 We can count them as the same thing. 75 00:06:13,970 --> 00:06:16,930 We can just account if we get a single node, which is one level. 76 00:06:17,210 --> 00:06:20,840 We also want to return back as the answer three. 77 00:06:21,920 --> 00:06:25,860 So here we have pretty good test cases to start working on a solution. 78 00:06:26,630 --> 00:06:30,250 Now I do want to challenge you to try and come up with your own logical solution. 79 00:06:30,770 --> 00:06:36,590 All of those techniques and all of the strategies that we learned with single link lists are still applicable 80 00:06:36,590 --> 00:06:36,880 here. 81 00:06:37,100 --> 00:06:43,070 We're still trying to figure out how to traverse from the very head of our linked list onwards to the 82 00:06:43,070 --> 00:06:44,060 next nodes. 83 00:06:44,180 --> 00:06:46,490 It's just that from here we have multiple directions. 84 00:06:46,490 --> 00:06:49,640 We can go, we can go backwards, we can go forwards. 85 00:06:49,640 --> 00:06:53,090 We can also go potentially down if there is a child. 86 00:06:53,900 --> 00:06:59,180 The thing that's important to note is that because we have the new previous property as well as the 87 00:06:59,180 --> 00:07:02,990 child property, we need to think about the appropriate things to do with these pointers. 88 00:07:03,410 --> 00:07:07,640 Let's say we're merging the seven, eight and nine into the two and three. 89 00:07:08,180 --> 00:07:13,480 This means that you need to remember that the Sevan's previous property needs to point to the to the 90 00:07:13,850 --> 00:07:15,620 next property doesn't point to three anymore. 91 00:07:15,620 --> 00:07:18,110 It points to seven, which was its child before. 92 00:07:18,500 --> 00:07:27,050 The child needs to get pointing to null, the nine needs to point to two's previous next value. 93 00:07:28,370 --> 00:07:34,100 Then three is previous value needs to point to the nine as well, so these are all the additional pointers 94 00:07:34,100 --> 00:07:34,870 need to count for. 95 00:07:34,880 --> 00:07:39,140 But remember, the more you sit with the and the more you struggle and fight with it, the more it'll 96 00:07:39,140 --> 00:07:39,740 make sense. 97 00:07:39,740 --> 00:07:45,560 And the more we practice our critical thinking, our critical thinking is going to be the most valuable 98 00:07:45,560 --> 00:07:47,480 tool for us with these interview questions. 99 00:07:47,720 --> 00:07:53,090 Just walking through this step by step and just trying to draw insights about what the logical steps 100 00:07:53,090 --> 00:07:56,440 to do are are going to help you get to the solution. 101 00:07:56,870 --> 00:07:59,620 And remember, with Linklaters questions, it's all about traversal. 102 00:07:59,660 --> 00:08:05,420 It's about traversing one note at a time, trying to figure out, based on the conditions of this note, 103 00:08:05,420 --> 00:08:09,540 having a child, for example, what things do I need to keep track of? 104 00:08:09,890 --> 00:08:12,830 Do I need to advance my notes any further? 105 00:08:12,830 --> 00:08:14,050 Do I need a new pointer? 106 00:08:14,060 --> 00:08:16,700 These are all considerations you have to think about. 107 00:08:17,510 --> 00:08:19,040 All of the tools are there for you. 108 00:08:19,040 --> 00:08:24,170 It's just about putting it together through fighting with the question and thinking about it critically. 109 00:08:24,590 --> 00:08:27,200 So spend some time and really try and think about this question. 110 00:08:27,200 --> 00:08:29,930 I promise you that it's a lot closer than you think. 111 00:08:30,350 --> 00:08:32,210 In the next lesson, I'm going to show it to you. 112 00:08:32,450 --> 00:08:33,710 So I'll see you in the next lesson.