The best way to begin your software engineer interview is to focus on finding a brute force solution first. This is the most important thing you can do. It will not only give you something to work with, but it also ensures that you actually have a working solution to the problem. There are a few ways to go about this, but I’m going to give you my favorite techniques for finding a brute force solution to any problem.

What you don’t want to do is get halfway through a solution and then realize that it doesn’t work. It’s much more important that you find something that works, because your interviewer needs to see how you can code, in addition to how you think about the problem. In my opinion, this is why it’s so important to start with a brute force solution.

So what is this technique?

This technique that I’m going to teach you works really well for any sort of problem where you are asked to generate all of “X” that has this property. An example where this would work is the stair step problem. In this problem you have a staircase of length “N” and you can either take steps of length one, length two, or length three. The idea is to come up with the total number of combinations of steps that you can take on this staircase. How can we begin to think about a brute force solution to this problem?

Staircase Problem

Using the staircase problem, you can very easily validate whether a given result is a valid or invalid set of steps. All you have to do is look at the distance between each step, and then make sure the maximum distance between the steps is less than three (for each step or each set of steps).

If this is the case then your input is valid and all you have to do is use a pretty standard technique to recursively generate all of the different combinations of possible steps. This allows you to get all of the possible results that you can, then filter using the validation function.

This is obviously not an efficient approach to this problem… but we are looking at the brute force solution to the staircase problem in this example, so it really doesn’t matter. In terms of finding all of those combinations, this is a technique that you are going to want to have memorized for your interview. You don’t want to have to think through that process in the interview, but to have a firm grasp on it going into your coding interview because it’s a standard recursive pattern that applies in many cases.

0-1 Knapsack Problem

Another example of a problem that follows a similar sort of structure is the 0-1 knapsack problem. In this problem you have a series of items that have a weight and a value. All you’re trying to do is figure out what is the combination of items that will give you the maximum value, under a certain weight.

You can easily figure out the brute force solution to the 0-1 knapsack problem if you have a combination of items to validate whether or not it’s a valid set of items. All you have to do is add up all the weights of those items and then check whether it’s under the maximum. Once you have the set of valid items, it’s easy to do basically the same thing to compute the values.

After that you just have to:

• Run the recursive function where you generate all of the combinations
• Validate
• Check which ones are under the maximum weight
• Find which of those is the biggest

That’s it!

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 inputs and different combinations that meet a set criteria, you can easily apply this technique. In some cases you can then optimize it slightly like in the staircase problem where you check that the steps are less than three apart and then do the recursion. As you get more advanced you can do that from the outset.

The same is true with the knapsack problem. As you’re doing the recursion you can continually check that the weight of your items is under the maximum weight of the knapsack. You can get slightly more optimal there, and in both of these specific cases, you can just use dynamic programming to then really optimize your solution. For more information on how to do that with dynamic programming, you can grab a copy of my free ebook.