Brute Force

[00:00:00]
>> Bianca Gandolfo: However, there's a problem. Would this approach work with these values of the coins, what if the input was 21 and the coin values were 10, 6 and 1? This is where the greedy approach breaks down. And this is why I'm not very pro using the greedy approach in an interview setting because it can seem like it's correct, but it's also hard to prove that it's correct and that's just a part of greedy algorithms.

[00:00:34]
In general, you kind of have to think of all the scenarios where it isn't correct versus just finding one correct answer and it being the correct answer. With a lot of algorithms, you can just know that. With the greedy solution, you have to say, is the locally optimal solution actually the globally optimal solution?

[00:00:53]
And sometimes, it will feel like it is, and it's not. And so there's this job scheduling problem that is very common when we're talking about greedy algorithms. And there's four different ways that you can go about doing that. Three of them are wrong, so just be aware of that when you're in an interview and you're like, this seems like a classic greedy algorithm.

[00:01:22]
Just know that there's a lot of ways you can go wrong. And so that's why I think we should just do brute force, which is to just go through every different combination of them. And then when you're introducing, I'm gonna just go with a brute force solution at first, and then I'll optimize after.

[00:01:45]
It'll be fine, at least you have some solution that's correct. And what's an algorithm if it's not correct, right? I guess in some scenarios, it's okay if it's not totally correct. In those scenarios where I mentioned before where the input size is so big that you can't actually find the correct answer, anyway, or you can't really know for sure if something is the correct answer.

[00:02:04]
There are still these unsolved mysteries in computer science. But, so for this scenario, our brute force approach is we're gonna calculate every single combination and keep track of the minimum combination of points. So what does that look like? Yes, it's recursion, it is. So we are going to, at every step, figure out all the different scenarios.

[00:02:36]
So the very first step, we can subtract all three. So we're going to go down to each of these decision trees and add up the one that is the least. And you can see, it's kind of, the depth of the recursion for each decision tree is the same as the number of decisions that are made.

[00:02:55]
So you can see that our best solution is 12- 6- 6, which is two coins. So you can think of it like that, or we could look at the actual code and we can play our favorite game. You guys are gonna hate this game after this class. It's so useful, especially with something like this when you have a bunch, you think that merge sort branching, just wait.

[00:03:29]
Just kidding, it's not that bad. Okay, so let's make some change. Maybe we'll just use our example as 12, keep it consistent. So this one is really cool, because we have a forEach in here. Remember we were talking about the forEach making things a little bit more complicated?

[00:03:55]
Here we are. Okay, so we're gonna makeChange, our value is 12. This has a recursion counter. I'm just gonna take this out.
>> Bianca Gandolfo: This is just, I have console logs for my examples so that you guys can run them and kind of see some helpful console logs. Okay, so we see our base case is when our value is zero, so we're gonna keep subtracting our coins from our value until we hit zero.

[00:04:31]
Once we hit zero, that's our base case, we return up. All right, so we're gonna initialize our minCoins. Sometimes I'll do minCoins -1, I think that's better. But that's okay. So let me just remove my, okay. So, we're gonna loop through all of the coins which,
>> Bianca Gandolfo: We have here.

[00:04:59]
Here are our coins. So for our first coin, we'll start with 10. And we're gonna say ( value- coin ), so here's our ( value- coin ) is gonna give us 2. So then, we call makeChange,
>> Bianca Gandolfo: Here,
>> Bianca Gandolfo: Where our value is 2.
>> Bianca Gandolfo: All right, so it's not 0.

[00:05:31]
Gonna initialize this, again, it's in its own little scope universe. And we have our coin, and then we're gonna start with 10 again.
>> Bianca Gandolfo: However, we don't ever go into this if block because the coin is bigger than 2. Or this condition is not met, so we're gonna go to 6.

[00:05:57]
Condition still not met, so we go to 1. Then we do our recursion again. Put the value one,
>> Bianca Gandolfo: And,
>> Bianca Gandolfo: Still not there. Initialize that, we're gonna start with ten. That's not gonna work, we're gonna start with. Then we're gonna do six, that one's not gonna work.

[00:06:18]
Then we finally get to one, great. Now we can do, cuz ( 1- 1 ) is 0, so it meets our requirements. So, we hit our base case, which is 0, so we're gonna return that. We're returning 0 from where we left off. So this, so makeChange(0), which is what we just calculated, equals 0.

[00:06:48]
So I'm gonna update that value to 0.
>> Bianca Gandolfo: And then, we're gonna continue on. So if the minimum coins is undefined, which it is, we are going to enter in here and we're gonna have our minimum coins equal our current minimum coins. So this is now zero, cool.

[00:07:06]
So, then we're gonna loop again. Actually we're gonna break through this loop, we're done, cuz we already looped through all of the values and then we're gonna return minCoins + 1, which is what? One, yeah, so we're gonna pop this off our stack.
>> Bianca Gandolfo: And this, so makeChange(1) equals 1.

[00:07:33]
minCoins, is minCoins undefined? Yes, even though we defined it in the previous stack, we popped it off, that doesn't exist anymore. They don't share the state at all. They're separate. So minCoins is undefined, and so we're gonna set it again. Our currMinCoins is now going to be 1.

[00:07:56]
So I think, yeah, we looped through everything. And now we're gonna return minCoins + 1, which is 2. Pop that off.
>> Bianca Gandolfo: So, makeChange(2) is 2. Following? Everyone good? Is minCoin undefined? Yes.
>> Bianca Gandolfo: So, we're gonna set our minCoins to our currMinCoins, which is 2. And then, so we reached the bottom of one of our branches here.

[00:08:36]
>> Bianca Gandolfo: So, we did 12 -10, -1, -1. And we recursed up, and now we're back here, and now we're about to go down through the 6. Everyone following how this is,
>> Bianca Gandolfo: Keeping track? Okay, now, we're going to, so we did 10. Now we're going to six.
>> Bianca Gandolfo: Okay, 6- 12 is 6, and so we're going to, sorry, I shouldn't have actually changed that.

[00:09:24]
makeChange(6).
>> Bianca Gandolfo: So and as you can see, we are now going here. So we subtracted 6. However, the next thing that we're gonna do, actually, no, this will work. It's gonna be perfect. Okay. So we have 6. The first coin is 10, that's not gonna work. Next coin is gonna be 6.

[00:09:56]
So we're gonna makeChange(6-6), which is 0. You guys remember what that returns? It's gonna return 0. So is minCoins undefined? Yes. So minCoins now equals currMinCoins, which is 0. And then we go to the next loop, which is one. And now we are, so we already returned here and we're going to go here and then this goes super deep, so I'm not gonna keep going.

[00:10:39]
But the key here is if it's not undefined, okay? Which it's not, it's 0. That's why it's important that this is triple equals undefined, and not something like this. This is a common bug because if it's 0, it's gonna be false e2. So make sure that it's explicitly set to undefined.

[00:11:01]
Sometimes I do negative 1 here as well instead of checking for undefined. It's gonna say, if currMinCoin, which again is just gonna be makeChange(5) less than minCoins. No, it's not. We know that because we have to make all of these coins. So five is really gonna be five one coin.

[00:11:25]
So this is gonna be five, so six different coins just to make this branch. And that's not less than zero, I know what you're thinking. Wait, but isn't it supposed to be two? How did we even get there?
>> Bianca Gandolfo: And it is because,
>> Bianca Gandolfo: What, where did we, how did we get there actually?

[00:11:49]
Hm, I think I skipped a step. Anyway, it's always gonna be, as we loop through here, it's always gonna be one less than what it is, and at the very end, I see. At the very end we're gonna add one, up the stack. So we're gonna add one, because we're gonna go through here, we're gonna do all these calculations, but we're never gonna set minCoins to whatever this returns.

[00:12:18]
And that's simply because currMinCoins is not gonna be less than zero. But we're still calculating all of that. So, we return minCoins + 1, which is 1, up here, and then minCoins. So, is currMinCoins less than minCoins? Right, it's 1, yes? So we're gonna update this, here, this line is updating it to 1.

[00:12:42]
And then it has to also do all of these and it's gonna go all the way down here and do a bunch of bunch of calculations. But it's not gonna be less, and so it's gonna say is the current minCoins of, makeChange(11), gonna be less than 1? Definitely not.

[00:13:03]
So then we get to the bottom, we increment it by 1 and then we have our solution, which is 2. So this is called brute force, and you can see why it is. Because it takes a lot of time to go through and calculate every single combination. And so-

[00:13:19]
>> Speaker 2: [INAUDIBLE] assess the time complexity of something like this?
>> Bianca Gandolfo: It's exponential, yeah, yeah. And so, given certain data sets, it's fine. You can make it work. However, with even moderate sized data sets, it can be too long, which is why sometimes greedy might not be the most optimal or correct solution, but it might be the good enough solution, a solution for it.

[00:13:50]
So there is our brute force solution, okay, yeah?
>> Speaker 3: Why are you making sure that the least number of bills is divisible by five?
>> Bianca Gandolfo: For the different one is not divisible by five.
>> Speaker 3: For the one-
>> Bianca Gandolfo: The one that we just did, yeah, that one is any one.

[00:14:16]
But yeah, for the original solution with the five there, I wasn't really checking. I was just assuming. It was the assumption is all the inputs would be the divisible by 5. But yeah, that's a good thing to ask your interviewer, actually. Should I do a check here or should I just assume that the inputs are gonna conform to my expectations?

[00:14:37]
And they're probably gonna be like, you should probably check for it. Because it's not reasonable to expect external data to conform to any sort of expectations. So you kinda have to check those edge cases. That's a good question.