Four Semesters of Computer Science in 5 Hours Median Values

[00:00:00]
>> [MUSIC]

[00:00:03]
>> Brian Holt: I told you about like I think it's dumb that people ask these questions in interviews but I wanna give you an example that no one's going to ask you to implement merge sort or if they do that's a really dumb question because you can just like Google that in ten seconds right.

[00:00:19] What's more important that you're getting out of this is not necessarily the rote repetition of the writing merge sort right because in reality you're never going to write merge sort in your entire career. You really shouldn't because someone else wrote it and they actually went through and did all the micro optimizations for you.

[00:00:34] See you don't have to worry about should I be cashing this or memorizing this or something like that. But what is interesting and what is useful about learning algorithms is you can kind of deconstruct these algorithms and use them in different places. Let's look at this. This is actually, it actually might even still be the interview question that read it.

[00:00:56] If the interview and read it like here you go here's one of the answer to these questions. This is what they asked me and as far as I know they still are asking it. They might get mad at me for you know putting it on video but whatever I don't work there anymore so [LAUGH] it's totally cool.

[00:01:09]
>> [SOUND].
>> Brian Holt: The question is I give you two sorted arrays, and I want you to find the median element between the two arrays. Now if you don't remember statistics the median element is the middle one. It's the middle index. And whereas it's not the average I average you add them all together and divide.

[00:01:35] If I give you two sorted arrays and I ask you to find the median element between the two arrays, I want one median element for the two arrays, how are you gonna do that? [COUGH]. Let's go through a couple different solutions to that, the naive answer is I'm just gonna concatenate sort and find the median, like that works.

[00:01:55] If I have, let's just write down two arrays here. We have 1, 5, 8, 9, and we have 2, 3, 7,10 something like that. If I just call concatenate sort I'm gonna get 1, 2, 3, 5, 7, 8, 9, 10 and then I can just ask what's up the fifth index or whatever?

[00:02:29] Yeah fifth index not fifth index the 5 index, the no, the four index the fifth element there we go. Okay. Check. Got it. Nailed it. [COUGH]. And that's fine that works but that's really inefficient, like that's that's the most inefficient way to solve this problem. What happens if you have 2 million indexes?

[00:02:51] That's a really, really inefficient thing for you to be doing cause you're gonna take up a ton of space in memory. You're gonna be taking up a lot of CPU cycles unnecessarily sorting everything. Well, this might look a little bit familiar. We have two sorted arrays that I'm giving you.

[00:03:07] What is this like? This is kinda like the stitch algorithm that you and I just did together. It's pretty similar that we have two sorted arrays. And that's exactly what that stitching algorithm does. Why then instead of concatting and sorting why don't we just do the sort kind of on the fly.

[00:03:23] We just do okay, is one or two greater one or two is greater? I'm gonna take 1 then take 2 and take 3 and take 5, 7, 8, 9, 10. Okay, so I have this new array that I didn't have to concatenate and sort it. I just kinda did that on the fly so now I can just give you the middle one which in this particular case is gonna be, yeah.

[00:03:50] I mean, in this particular case you take 5 or 7 or you do the, you'd get six. I don't care about statistics, so whatever. Whatever you feel like giving me is fine. We can make this still a bit better though? Because if you think about it, the median element is going to be always, a 100% of the time, the fifth element in there.

[00:04:15] We actually don't need to create new array or anything like that. We can actually just count and as soon as we get to the fifth item in the sorted array, we can just stop because that's it. We already found it. I can just say, I don't have to create anything new in terms of array.

[00:04:30] I can just say, okay well, 1, 2, 3, four wait a minute yeah, 5 and I don't have to care about the rest of them that's it, that's the end, that's the answer. I'm hoping this demonstrates to you that these algorithms you can kind of pick them apart and take these constructs, these ideas, these concepts, and apply them to different parts of your your computing.

[00:04:58] As you learn these algorithms you're gonna learn novel ways to apply them, and to take these classic computer science ideas. These were all invented in 60s, 70s, 50s, whatever and some of them even earlier cause they're mathematical concepts and not computing concepts, and apply them to whatever you're doing.

[00:05:15] And so a lot of your interview questions are gonna be derivatives of this cause again, this was not invented here, this is a merge sort of thing and we're just kind of taking part of that out and using it here.