Two Crystal Balls Problem

[00:00:00]
>> All right, so let's go on to the next part. So I'm gonna actually give you an interview question that I had at my first job. This involves arrays, it's also a question that I happened to have in computational theory, which I thought was fantastic. Given 2 crystal balls that will break if dropped from a high enough distance, determine the exact spot in which they'll break in the most optimized way.

[00:00:24]
Often, you'll hear something like you're in 100 storey building and you have 2 crystal balls and you wanna find out which floor do they break. So what's the most efficient way to do it in 100 storey building? This is just the generalized version of the exact same thing right here.

[00:00:40]
So let's do the generalized version cuz we're computer scientists, we generalize. We're not gonna do the weak version. So let's discuss our options we have. We right now know of both linear and binary searching. So let's kind of talk about them and their associated time constraints. So if we generalize this problem, really, when you really think about it, what it is.

[00:01:03]
It's an array full of falses, right? That at some point it becomes true and from there on out, it's true, right? And we're trying to find, where is this midpoint? Or where is this point? It doesn't have to be mean. There's just a point in which no matter how much higher you go, your crystal ball breaks every single time.

[00:01:20]
There's a point before, where it doesn't break. Now, despite what Elon Musk says about Cybertruck, if you drop this crystal ball over and over again it won't break. I swear that was a great joke, we just made that one up. I feel very good about that. All right, so what we wanna do is find this in the most optimized way, right?

[00:01:36]
And so if we start off at 0 and just linearly walk, yes, we will find it, correct. We will eventually get the true, it will break. But we are given a constraint and we really didn't even use our constraint, which is we have 2 crystal balls, I apparently can't spell crystal.

[00:01:54]
We have two of them, right? So, therefore, we should be able to do something more efficient than that, right? Because if we linearly walk and find t, what is the runtime of the algorithm? Imagine in your head what you're gonna write, you're gonna write a for loop, right?

[00:02:12]
You're gonna write a for loop over the space of the array, checking every single time. It's a loop. Trick, look for loops, there's a loop based on the input, boom, linear, right? It's O of N. Very, very simple to see. Okay, we're like, whoa, whoa, whoa, whoa, we are so much smarter now.

[00:02:29]
We already know something. This array is ordered, right? If we break it down in the most ordinary kind of way, it's this, right? It's a bunch of 0s, until it's a bunch of 1s. We're so much smarter than this, we can easily do this. So, again, we have an array.

[00:02:44]
We jump to the middle and we're like, hey, Xi, are you true? And it's like, yes. No, what just happened there? Well, 1 of our 2 crystal balls just broke. And so therefore, what do we have to do with the remaining 1? We have to linearly walk from our last known good point until we hit a bad point.

[00:03:10]
And if we walk one half of N, what's the running time of that? Remember, rule two. Yeah, dropped the constants, bam, drove, dang it, I drew on the line. Bam, right, there you go. You've just dropped the constant and it's back to end. So both of our searches suck, right?

[00:03:30]
Neither of them work. I really wanted to work this one in here because specifically during the interviewer or during the interview, the interviewer did not know the generalized answer. And when I just said it right away cuz I was so stoked, they said, well, that's not the answer.

[00:03:42]
I said, it is the answer and here's why. It was so exciting. So what do we have to do here? Well, the reality to the answer is this, is that we have to jump in such a way that isn't some portion of N that means we have to walk some portion of N.

[00:03:57]
We need to be able to jump by a fundamentally different unit. Does that make sense? So normally what we did in binaries, we cut the space in half. That makes it really, really efficient. But in this case, we're jumping, so we need to do something different. So here's what I propose.

[00:04:14]
We jump the square root of N, the square root of N, right? And so that means we're gonna jump a square root amount of times until it breaks. And if it breaks, we have to walk backwards to our last known good point and find the point of breaking.

[00:04:30]
If we walk back and we have to walk forward, how much are we going to walk forward at most? The square root of N. So what is the running time of having to do a square root of N plus a square root of N worst case, right? Cuz we could have to do a square root of N jumps until we're off the board, back it up by square root of N and walk square root of N.

[00:04:56]
So what is the time of this?
>> The square root of N.
>> The square root of N. Look how fantastic that is. We actually did it. Now, you don't have to write it like this cuz, of course, you can rewrite that as the two square root of N and so what you do, you drop the 2, so up, up, up, up.

[00:05:10]
We have just come up with a new running time that you probably will never see again, but this is a fantastic little exercise. Which is we now have just broken down a search problem without doing a linear search. And I think that that's really kind of a cool thing.

[00:05:25]
I love these type of tricks cuz often they will expand my mind for me to be able to use this in other areas. If I see something that I can't use, say, a priority queue, which we'll talk about, and I need to be able to search in such a unique way, I have one more trick inside my bag.

[00:05:38]
And it's always good to have one more trick inside of the bag.