Golden Weighted Ball Problem

[00:00:00]
>> I wanted to give you a visualization of thinking through these different mechanisms, these different techniques. There's a logic problem that I was presented in a job interview 20-something years ago. And I, after being presented this, almost immediately started using it myself when I gave job interviews because I just loved the idea of this problem and what it illustrates.

[00:00:27]
And so some of you may have heard it. Some of you may have never, it's the problem of the eight golden spheres. And we have eight golden spheres here and we have a traditional balance scale, meaning that it is only balanced when the weight on both sides of the scale is equal.

[00:00:42]
What we're told about these golden spheres is that they are identical in texture, size, shape, color, everything, except one of the eight. We don't know which is imperceptibly lighter than the other seven. That's the only thing that we know about the problem. We know that one of them weighs a little bit less not enough that you could hold it in your hand and tell?

[00:01:10]
But we know that one of them is less than the problem is how do we find it? How do we find the odd one out? How do we find the lighter one? There are multiple ways to solve this problem. But when presented in a job interview, what they're kind of looking for is like how do you translate a real world problem?

[00:01:27]
Into an algorithm, into data structure and algorithm approaches. So rather than put you on the spot, some of you are still working through your first cup of coffee rather than put you on the spot. I'm gonna walk you through three different ways to solve this problem. We get three different answers to it.

[00:01:43]
But the basic setup is how do I use this balance scale to guarantee in the worst case that I find the odd ball out. And what's the minimum, worst case number of usages of the balance scale to get that? So perhaps some of you are thinking right off the bat, I'll stick one ball on either side of the balance scale.

[00:02:09]
And if they're equal, then I've eliminated those two because neither one of them can be the one. If they're unequal, then I immediately know which one was lighter. It's the one that went up. In the worst case, they were equal, so I need to go on to two more.

[00:02:25]
And in the worst case, those were also equal, so I go on to two more. And in the worst case, I've eliminated six now. Have used the balance scale three times. And on this final fourth time, I'm guaranteed to know which one was the lightest. So in the worst case, we used it four times.

[00:02:40]
And this is an iterative approach to the problem. We took two elements, we compared them. We kept going until we had gone potentially worst case through the entire data set. And we have guaranteed ourselves that we found it similar to a search algorithm, iteratively going through this is effectively a search algorithm, right.

[00:03:00]
So a lot of times in a job interview, somebody says, 4, that's the answer. That's the minimum number of usages. And the interviewer might nod and say, that's a good answer. But if I told you that there's a way to do it in fewer usages, how would you do that?

[00:03:17]
Okay, so let's flip the script around a little bit. Instead of starting with one on each side, let's start with more than one on each side. In fact, let's start with four on each one. Right, we've got eight balls. Let's divide it in half. We'll put four on one side, four on the other side.

[00:03:33]
Now, what this usage of the scale is gonna tell me is that I know that the lighter one is in a set of four. It's on one side of the other. But I don't yet know which one it is. I've just narrowed my problem down. You follow me?

[00:03:49]
So let's say it was the left hand side that was lighter, then we take those four and we split them in half and we put two and two. Now I've eliminated two more, I've eliminated a total of six, I'm left with only two balls for sure. I know it's one of those two, I put them on the scale a final time.

[00:04:07]
Now I've used the scale three times and this is the binary search, it's recursive solution to the problem. So when you're on a job interview and somebody's asked you this, and you might jump immediately to the recursive. But many people jump first to the iterative, and then they realize, I could have done it recursively.

[00:04:25]
And so they got it down from four usages to three. We have a more optimal algorithm. But then the interviewer gets a little glimmer in their eye and he says, what if I can tell you that it can be done in fewer usages? How would you do it in fewer?

[00:04:41]
We went from one and one all the way to the other side doing it in four and four. We can't do more than that. We can't do like eight and eight, cuz there's only eight total. So by process of what we call discrete math, there's only two other choices, right?

[00:04:55]
We can't put an uneven number of balls in the scale. That's not gonna tell us anything, they have to be even so we can either put two and two and you could run through that mental exercise. I didn't create that as a slide but you could either put two and two or you could put 3 and 3 so, let's just try 3 and 3.

[00:05:11]
We're gonna put three on either side. Now, what's gonna happen? There's two possible outcomes, either we're going to see the balance scale completely balanced, which means we have eliminated six of our balls. And in that case, we only have two left, we only need to use the scale one more time to identify the odd ball out.

[00:05:31]
You follow me? But what if one side is uneven? How many have we eliminated in that case? Let me see if you're awake. If we put three and three on there and the scale is not balanced, how many balls have we eliminated by that usage? Five, good. Five because we have the three that we know are heavier.

[00:05:57]
And the other two that we didn't even try, we know that they're not it. We know that the problem ball, or the odd ball is in this set of three. But that's not an even number. How are we gonna use the scale? Well, we've used it once. And now we've narrowed our problem down to three.

[00:06:15]
Now you simply pick any two and weigh them. If they are even, you know by process of elimination it's the one you didn't try. If they're uneven, you know that it's the one that's lighter. So in the worst case scenario, we only had to use the scale twice.

[00:06:33]
So what is this algorithm called I call it the fuzzy search algorithm I don't know but can you see how we thought a little bit outside of the box. We asked something more of our problem which is it definitely true that I can only use the scale with an even number.

[00:06:53]
We understood something about the nature of, again, what we call discrete math. You can't divide the balls, so we only have a fixed number of possible balls to ever put into this problem. Now let us know that we have one on either side, two on either side, three on either side, or four on either side.

[00:07:11]
That's our fixed problem space. So we could examine that in both cases. A lot of times when somebody's faced with this on a job interview, they kind of tense up and get a little bit frustrated. And something as basic as that, all you have to do is try the four possible things.

[00:07:29]
You don't have to solve for millions of possible combinations. There's only four possible. If you have a computer science background, that immediately jumps out to you as a discrete math principle, similar to the birthday problem. If you heard the birthday problem, which says that if you have 95% or if you have more than 30 people in a room.

[00:07:50]
There's a 95% chance that at least two people in the room have the same birthday. And we actually solved that. I'm not gonna do it here for you. But the derivation of that answer is actually discrete math. So when you have a more formal background, some of that might jump out.

[00:08:09]
But even if you didn't have the formal computer science background, you can reason about the idea and ask the question, am I allowed to divide the ball? Am I allowed to divide the sphere? No, okay, that tells me something pretty important. What it tells me is that I can only put even numbers of things on there.

[00:08:26]
I can't divide the balls into half and half or whatever,okay? So asking those questions and understanding the answers to those questions will guide us to very different solutions to the problem. In this case, four versus three versus two not a big deal, but the principle underlying it is the principle that as an algorithm and the engineer.

[00:08:47]
We need to get comfortable with.