Implementing Two Crystal Balls

[00:00:00]
>> We'll implement it cuz it's so exciting, I really think it's exciting. I think this is a good exercise to go over, so again, open this up, search crystal balls, there we go. And so I'm gonna pass in the breaks array boolean and you're gonna return back out the index into this array.

[00:00:16]
So remember, just like our algorithm, we want to jump by the square root of N, and so how do we do that? Well, it's pretty straightforward. Constant jump, amount will equal math.sqrt (breaks,length), right? But we can't really use just that cuz what's the square root of 3? I don't know, right?

[00:00:38]
I'm not that smart, so therefore, let's become that smart and let's use the floor unit. Let's assume that the array is big enough to have a square root. There we go, right, it's gonna be effectively one for three, there we go. So we now have our jump amount, the amount we wanna jump, so what's the first step?

[00:00:56]
We use our first crystal ball to see where does it break? So I'll go like this, let i equals jump amount. We have a question.
>> Why suddenly square root and not having like before?
>> Okay, yes, so I did the worst case right here. So here's why having doesn't work.

[00:01:17]
If you jump to your middle element and your ball breaks, what does that mean? Well that means you only have one left. Therefore, you need to start from a last known good position, which is zero in this case and walk to half of N. Half of N walking half of n is still linear time, we want to improve linear time.

[00:01:40]
And so that's why it is better to jump by a different amount. So jumping by the square root of N means that we will at most walk square root of N. Or in other words, the worst possible case is square root of N amount of jumps until we're off the array, go back square root of N and walk square root of N.

[00:02:00]
That makes sense? Whereas the worst case having is that you have to walk half the array. There we go, so I is the amount we want to jump, we're gonna start at the first jump cuz it will make sense for i has to be less than brakes length, i plus equals jump amount.

[00:02:19]
There we go, and so now we just simply try to wait until we break, okay, so if breaks i then break, oops I just replace that. There we go, now we do exactly what we said. We find the point where it breaks, we walk back, we jump back square root of n, then we walk forward square root of n.

[00:02:40]
So, i minus equals jump amount, there we go, and now we've just jumped back square root of n. Now we just simply need the walk forward square root of n. So for let j equals zero, j has to be less than jump amount, and we'll go like this.

[00:02:59]
I have to be less than brakes length just in case we walk off our board, we don't wanna walk off our board. And then we can just go plus plus j, awesome. So now we're gonna make sure we walk maximum a jump amount of steps. If {breaks[i]}, oop, I forgot one thing, ++i], there we go.

[00:03:19]
If we find the breaking point there we go we can literally just return it at this point or we can return negative one, right there you go that should be the answer. I always get so nervous about the wrong answer, here we go, two, I think that's all we have to type.

[00:03:38]
My goodness, it worked out again, so there we go. So here's the simple code, which again we did it in the exact same steps. I'm gonna jump over here, we first walk by the square root of n jumping square root of n at a time exact same thing you see right here.

[00:03:53]
We set our initial jump point or our initial point to the square root of n we then check for breaks and jumps square root of n. We jump back a square root of n, then we linearly walk forward at most, a square root of n until we find a break.

[00:04:08]
At that point, we either return I at this moment, which is the index in which it breaks or we return -1, hopefully that all makes sense. It's a pretty fun algorithm to kind of think of, I think it's a really kind of a challenging one too cuz it just changes kind of how you view it.

[00:04:24]
And you never know I was asked this question maybe one day you guys will get asked this question. Likely not now that's on the internet completely ruined it, but it's a fun one. So I've already said I've had this one. Look at that even did the binary search and Google Docs, it's shocking how many times you'll get asked to do binary search at Google.

[00:04:41]
They just asked that question all the time so come prepared, be ready all right. All right so let's take a breath you get it good pun I thought it was good I think it's a great pun, I'm sure there is a lot of questions. This is a great stopping point for any questions we can have at this moment.

[00:05:00]
>> Can we still cube root of n stuff? Square root of n?
>> We could travel a cube root. I wouldn't know what the running time of that would be though, because that means you'd also have to hop cube root of times which is a higher amount of hopping.

[00:05:14]
Cube root-
>> Right.
>> Is smaller than the square root of n, right?
>> It is smaller, so your jumps become progressively smaller. I don't actually know what that proof would look like and why it would be faster or slower. To me, it seems like it'd be slower.

[00:05:28]
>> What if we go more than square? I'm just trying to figure out why we have chosen square root of n.
>> Square root of n, or the square root of n, it's just the only way we can change this from nonlinear running, right? Cuz if we use a binary search, we still run into a linear problem.

[00:05:41]
If we jump by some portion of n, we're still running linear. We wanna get sub-linear, we cannot get to log, but if we just do a cube root as add or a cube root. If we just do a root then we get the maximum on a jump right you get the maximum amount of distance with a still lower running time.

[00:05:57]
As you increase obviously your root level the closer you get to a linear run, right? So if you do the quad route then you get to the point where you're practically jumping by one, right? Then you do the next route you are definitely jumping by one if not by zero at that point right it's just like becomes nothing.

[00:06:12]
So it just I think it quickly approaches end.
>> Wishing their college professor was you back in the day.
>> I know and still, if this ever gets back to Montana State University Brocklin Mears best teacher ever. I model everything after him he got teacher of the Year Award once.

[00:06:29]
The man was writing on the he did Karnaugh maps he did digital logic all that he was writing on the board he was so excited that when he tried to write it launched out of his hand. And made it all the way across the room and I was just I was sitting there like so engaged going, this is how I want all my professors to be, right?

[00:06:45]
I want them to feel like they like what they're teaching. And I like what I'm teaching. So, I don't wanna, I'm showing you how much I like what I teach.