3 Steps To Solve Any Algorithm Interview Problem

So I published an article about how I thought that most interview questions are actually pretty useful as they test the candidate’s problem solving abilities.

It’s a good article, but when I published it I felt like something was missing. What if you don’t know how to solve these problems? What then?

Well, in this post I’m going to give 3 ways to solve pretty much any programming question. Or, said another way, this is everything I learned in my computer algorithms class in one blog article. And I paid how much for my University education?

1. Break It Down

Now before you start trying to apply more complicated algorithms to solving problems you’re going to want to try to solve the most basic version of the problem. This will already solve like 99% of problems.

So for the brackets problem in the original post:

How do you know the brackets in a string are valid? Well, the first thing I’d do is try the most basic string that would work.

It’s sort of like making a test case. In fact test cases are really useful for solving algorithm problems. That’s why we have test driven development, TDD. You write the tests before we write the code.

Now, it’s not always a good idea, especially with complex code involving many parts operating together. But algorithm questions are a perfect match for TDD because they are easy to test and they allow you to build up a partial solution to a full solution.

I actually do this a lot when writing functions that use a lot of math and can seem overwhelming. Especially in Python as doctests make it so easy.

So here we can consider a few simple test cases:

expect(isValid(“”), true) expect(isValid(“(“), false) expect(isValid(“()”), true) expect(isValid(“(()”), true) expect(isValid(“(())”), true) expect(isValid(“()()”), true)

So I’m ignoring the thing in the question that tells you it should work with 3 types of brackets because it’s a red herring. If you can do it with one bracket type you can do it with 3 or any number.

It might take a while to see this, but it’s not too hard to realize and it just makes it so you have to write more test cases.

So what can we see from these test cases? Well, immediately we can see that we need to somehow count the number of brackets. So let’s make an algorithm: count all the brackets and if the number of opening brackets is equal to the number of closing brackets return true. Else return false.

Now at this point we would begin trying to find a counter example. Some sort of string that passes our test but is invalid. And unfortunately we can pretty easily find one.

expect(“)(“, false)

But don’t worry, hope is not lost. We can try again taking what we learned from the previous attempt. So how do we do this? Well, our counter example tells us we need to somehow make sure every opening bracket has a closing bracket on the right.

So how do we do this? Well, we could make some sort of graph to point every opening bracket to its accompanying closing bracket. And there’s our algorithm. Of course we’d probably not want to program it with a literal graph because that’s a lot of work.

There are a few alternatives. First we could just brute force it by removing the bracket pairs one at a time like so:

”(()())” => ()() => () => empty

And this works. Another way we could do it is have some sort of counter to count the number of brackets that need to be closed. So like:

- Go through the string left to right
- If we see an opening bracket increment the count by one
- If we see a closed bracket decrement the count by one
- If the count ever goes below 0 or we end with a count above 0 it is an invalid string

2. Recursion

Now that is how you solve easy problems. Let’s get into the harder ones. Recursion. Now I would say ‘Divide and Conquer’ but I think a divide and conquer algorithm has some special meaning and not every recursive algorithm is a divide and conquer algorithm. Or something.

So let’s just talk about recursion. Recursion is, in my opinion, taught extremely poorly in schools. Because the classic example of recursion is factorial or Fibonacci. And, yeah, you can solve these problems with recursion. But why? You can do it with a loop just as easily.

The main power of recursion is actually traversing trees or anything with nodes. Is the node we’re at right now the correct node? No? Then just apply the exact same operation to the next node.

But I’m not going to talk about that, I’m going to talk about recursion and problem solving.

Recursion, once you know how to use it, is such a beautiful idea. At its core all recursive algorithms do something like this:

Can I solve this problem in one step?
  Yes -> Apply the step.
  No -> Try to make the problem smaller and try again.

Well, there are technically recursive algorithms that use 2 functions that call each other recursively but let’s not worry about them.

So this structure is beautiful because all you need to do are three things: determine if you can solve the problem in 1 step, actually solve it in one step if you can, and make the problem smaller.

So here’s an example I just did: diffing a single line. This is actually the algorithm I submitted to pip.

Say we have the lines: “I called but no one answered.” and “I tried calling, but no one answered.” and we want a graphical diff of these two lines. Something like:

I•••••• called•• but no one answered.
I tried calling, but no one answered.
 ^^^^^^     ^^^^ 

So how do we do this? It’s a pretty complicated problem and it took me a while to figure out how to solve it but with recursion it’s pretty easy.

Ask yourself: “I called but no one answered.” and “I tried calling, but no one answered.” can we do this in one step? Probably not. So we have to shrink the problem. How do we do that? Well, look at that substring, ‘ but no one answered.’ It’s the same in both strings. So we can be pretty sure that will be in our final solution so we don’t have to worry about that anymore.

This allows us to break the problem down into two smaller problems: everything before ‘but no one answered’ and everything after ‘but no one answered’. And there’s nothing after in this scenario so we can focus on only everything before.

So how do we handle “I called” and “I tried calling,”? Well, same thing: we notice “ call” appears in both. So we can remove that. Then we have “I” and “I tried”. “I” appears in both and we are left with “” and “ tried”.

Well, this we can solve in one step. One string is non-empty and the other is empty. So we just print some sort of indicator saying these are not the same string.

And in a similar way we do this with the rest of the strings. This gives us the following algorithm.

- If both substrings are empty return
- If there is a shared substring print that and recurse on the left and the right
- Otherwise just print out something fancy

Now we have a very complex algorithm that we can express in only a few lines of code. Recursion is magical.

Now recursion takes a leap of faith. Like, “How do we know this algorithm works for every input?” We don’t. I didn’t when I wrote it. It may just explode if we give it the wrong input.

I think that’s why recursion feels weird to people. You have to write the algorithm before you actually know it will work. And that’s weird. Well, you write a mathematical proof. But no one has time for that.

But anyways pretty much all the time if you follow these three steps: check if we can solve it in one step, if so solve it in one step, and if not reduce the input size and try again, you’re going to get an algorithm that works all the time except maybe in some edge cases.

3. Dynamic Programming

Now we’re getting serious. Probably 99.9% of programming problems can be solved by just breaking them down. Then 0.09% can be solved with simple recursion. The remaining 0.001% can be solved with dynamic programming.

Now I’ve never actually encountered a dynamic programming question in the wild. But it’s worth talking about how to solve them.

So at its core, dynamic programming is about breaking the problem into subproblems, solving the subproblems first, and then solving the main problem.

Now you may ask yourself, “Isn’t that just recursion?” Well, it’s similar but it’s more complicated. In recursion, we usually only take into account a fixed number of subproblems. Usually 2. In dynamic programming we usually have to take into account every previously computed subproblem.

Also in most normal recursive problems, the subproblem will be in the main problem. Like you diff a line a subproblem is a part of that line. But the subproblems are much less obvious in dynamic programming.

So the famous dynamic programming problem is pseudo polynomial knapsack. The knapsack problem is the question: given a knapsack of some maximum weight and a list of items each with a weight and a value what is the maximum value of stuff you can fit in the knapsack (duplicates are allowed)?

So the decision version of this problem is NP-complete. That means in order to find the optimal solution you have to try every single possible combination.

The pseudo polynomial version uses dynamic programming and is a bit smarter. Here’s the pseudo code:

- Make a list of the best possible value we can have for each capacity
- With capacity 0 we can at best have 0 items
- For capacity 1 we can have the most valuable combination of items with capacity 0 + the most valuable item with weight 1 (if it exists)
- For capacity 2 we can have the most valuable combination of items with capacity 0 + the most valuable item with weight 2 (if it exists) or the most valuable items with capacity 1 + the most valuable item with weight 1 (if it exists)
...
- For capacity N we can have everything from any of the previous capacities (i) + the most valuable item of weight N — i
- Go through all the arrangements and find the best one

So this is the general form of a dynamic programming problem. Solve the problem for size 0 then 1 then 2… N.

And surprisingly dynamic programming problems all look similar to this. They all have this property that you have to solve it for size 0,1,2… N. So there’s not really that much to say here.

You can imagine similar problems where a solution of size n contains the solution for some smaller value i. For example is there a route of exactly size N to get from one point to another. Calculate all the routes with size 1, 2,… n.

Also because of this property dynamic programming algorithms tend to have polynomial running time. Meaning these algorithms usually run in O(n^c) time. Which isn’t the greatest but at least you have some solution and that solution isn’t ‘try every possible combination’ which has an exponential running time.

Oh, and the reason this is pseudo polynomial and not polynomial (making N = NP) is because the running time is dependent on the capacity of the bag, not the overall size of the problem and we can have duplicates of items making it so we can increase the size of the problem exponentially with only a linear increase in the number of bits used to encode the problem. IE: knapsack(1000) is 1000 times harder to solve than knapsack(1) but the actual size of the problem is only 3 extra 0’s. 3 bits in base 10.

Conclusion

In my algorithms class I saw a bunch of other algorithms. But they’re mostly just common sense. Like a greedy algorithm. Just do the important stuff first. Duh!

Apart from just thinking about the problem, recursion and dynamic programming are the only algorithms that are genuinely difficult because you would not be able to come up with them if you did not know them. This is just because of how counterintuitive they are.

But I think these should be sufficient for pretty much any algorithm question. I mean they might not give you the fastest running time or space complexity. But I don’t really think running time or space complexity problems are a good indicator of a programmer’s ability.

And using these techniques you should be able to make an algorithm that performs reasonably fast anyways.

Wait. Before you go why not give this article a clap or two.