fbpx

Finding a brute force solution

What's up everyone. Sam here from Byte-by-Byte.com and today I want to talk to you guys about one of my favorite techniques for coming up with a brute force solution to a problem. If you've been following me for any length of time hopefully you've heard me say by now that the most important thing that you need to do when starting an interview is come up with a brute force solution to the problem. I think this is so important not only because it gives you something to work with, but it also ensures that you actually have a working solution to the problem in your interview.

It's much more important that you get something done that works, then that you get halfway through a prob a solution that doesn't work. And that's because your interviewer needs to actually see how you can code in addition to how you can think about the problem. And it's just really important in my opinion to start with that brute force solution. So what is this technique that you can use? In this technique it really works well for any sort of problem where you are asked to generate all of X that has this property.

And so let me give you an example. Let's consider the stair step problem, which is this problem where you basically have a staircase of length N and you can either take steps of length one of length two or length three. And you basically want to come up with what is the total number of combinations of steps that you can take on this staircase. So how can we start thinking about a brute force solution to this problem? Well the first thing that we know is that if we have a staircase, any if we have a series of steps we can really easily validate whether that is a valid set of steps or whether that is an invalid set of steps. In this case all we have to do is look at the distance between the step each step and as long as the maximum distance between the steps is less than three for each step, or each you know set of steps. That means that our input is valid. And then all we really have to do is use this pretty standard technique to of recursively generating all of the different combinations of possible steps to then get all of the possible results and then filter it using that validation function that we have.

Now obviously this isn't a super efficient approach to this problem. But we are looking at the brute force solution here so it doesn't really matter. And in terms of finding all those combinations that is a technique that you're going to want to have pretty much memorized for your interview. You're not gonna want to have to think through that at the moment. And it's pretty standard recursive pattern that applies in a lot of cases.

So let's look at another example of a problem that follows a similar sort of structure. In this case we'll look at the zero-one knapsack problem. And in this problem you have a series of items that have a weight and a value. And all you're trying to do is figure out what is the maximum number or what is the combination of items that will give me the maximum value but are under a certain weight? So how can we find a brute force solution to this problem? Well it's easy for us if we have a combination of items to validate that whether or not it is a valid set of items. Because all we have to do is add up all the weights of these items and then check whether that's under our maximum. And once we have that set of valid items it's super easy for us to do basically the same thing to compute the values. So now all we have to do is run our recursive function where we generate all of the combinations then what we do is we validate, we check which ones are under the maximum weight. And then we just find which of those is the biggest.

And that's all we have to do. And this technique applies to so many different problems. Anytime you're trying to do something like this where you're looking at different combinations of the inputs and especially different combinations that meet some set of criteria, you can apply this technique. And you can even optimize it slightly in some cases you can like with the stair step problem you can actually check that these steps are less than three apart as you're doing the recursion. If you could start to get more advanced you can sort of do that from the outset. The same with the knapsack problem as you're doing the recursion you can continually check that the maximum weight is under or the weight of your items is under the maximum weight of the knapsack. And you can get slightly more optimal there and then in both of these particular cases you can just use dynamic programming to then really optimize your solution. And if you want to learn more about how to do that you can check out my ebook at DynamicProgrammingBook.com. And otherwise if you like this video please hit subscribe below and I hope to talk to you guys again soon.

Nail your coding interview and get the job you deserve

Sign up for my weekly emails and I’ll show you how to become an interview rockstar, solve brutal coding problems, and get the dev job you deserve.

We won't send you spam. Unsubscribe at any time. Powered by ConvertKit

Nail your coding interview and get the job you deserve

Sign up for my weekly emails and I’ll show you how to become an interview rockstar, solve brutal coding problems, and get the dev job you deserve.

We won't send you spam. Unsubscribe at any time. Powered by ConvertKit