Right before the holidays, I said that you had better learn how to solve programming problems.
This time I am going to try and give you some good tools to enable you to get good at solving programming problems. (Really algorithm type problems specifically.)
Common mistakes
When most programmers are given a programming problem in an interview, they make several key mistakes. The most severe of those is the improper allocation of time.
If you have heard the saying “measure twice and cut once,” then you are probably familiar with the idea of spending upfront time to make sure something is done right, rather than diving right in.
The most common mistake I see when conducting interviews or watching someone try to solve a programming problem is they try to start writing code as soon as possible.
You must resist this urge.
You really want to make sure you take enough time to understand the problem completely before attempting to solve it.
Another big mistake is trying to over solve the solution on the first iteration. Keep it simple, don’t try to get fancy.
A simple set of steps
I am going to give you a simple set of steps to follow which you can use for any algorithm type programming problem.
- Read the problem completely twice.
- Solve the problem manually with 3 sets of sample data.
- Optimize the manual steps.
- Write the manual steps as comments or pseudo-code.
- Replace the comments or pseudo-code with real code.
- Optimize the real code.
As much as 70% of our time should be spent in steps 1-3.
Let’s look at each step.
Read the problem completely twice
This is the single most important step. You may even want to read the problem 3 or 4 times.
You want to make sure you completely understand the problem. A good test of this is whether or not you can explain the problem to someone else.
I cannot over-emphasize how important this step is!
If you don’t understand the problem, you cannot solve it. Do not worry about wasting time here, because the better you understand the problem, the easier it will be to solve it.
If you are given any examples along with the problem, make sure you have worked through the examples and understand why the answers are correct for each one.
Solve the problem manually
“Nothing can be automated that cannot be done manually!”
Programming is automation plain and simple. You may have the ability to skip the manual steps and jump directly to code, but there is a manual process which is the foundation of any code you write.
It is very important to solve the problem manually first, so that you know what you are going to automate, otherwise you are just slinging code around. Which while can be fun, will make you look like an idiot in a programming interview and will probably cause you to sweat profusely.
I recommend that you solve the problem with at least three different inputs to make sure you really understand your solution and that it will work for more than one case.
I often use a Mathematical Induction approach if possible. Using this approach I might try and solve for 1 first, then for 2, then for n.
Also don’t forget to look for corner cases and edge cases and do any examples for those kind of cases you can think of.
It’s very important that when you solve a problem manually, you recognize what your brain is actually doing to solve the problem. You may need to write out all the things you are normally storing in your head. You want to be aware of each step, it is easy to gloss over them.
Let’s look at a very basic example, reversing a string.
If I give you a string “Zebra”, and ask you to reverse it, most people will do the following manual steps.
- Write “Zebra” down.
- Start a new word, and put “a” as the first letter. (Why –> because it is the last letter, we want to start here)
- Put “r” down as the 2nd letter. (Why –> because it is the next letter backwards from the last letter we copied)
- Put “b” down as the 3rd letter. (Why –> same as above)
- Etc
Notice how I write down each little step and why.
Optimize the manual solution
People often don’t realize how valuable this step is. It is much easier to rearrange and reconstruct and idea or algorithm in your head than it is in code.
It’s well worth the effort to try and optimize the actual solution or simplify it when it is still in the most easily malleable state.
What you want to do here is figure out if there is another way you can solve the problem easier, or if there are some steps you can cut our or simplify.
Let’s look at our string reversal example and see if we can simplify the steps.
We should be able to immediately recognize that we can use a loop here to reduce the manual steps. Our duplicate why’s for most of our steps tell us that we are doing the same thing over and over for each step, just with different data.
- Write “Zebra” down.
- Start at the last letter in the word and create a new empty word.
- Append the current letter to the new word
- If there is a previous letter, make the previous letter the current letter and start back at 3.
Look how close we are getting to code at this point. You should be tempted to actually write the code for this. That is good, it tells you that you have solved and simplified the problem well. Writing code should now become very easy.
Write pseudo-code or comments
Many times you can skip this step if you have a really good handle on the problem or your previous steps already created a detailed enough description of the solution that coding it is already a 1 to 1 translation.
If you are a beginner or struggle with these kinds of problems, I would go ahead and take the time to do this step anyway though.
What we want to do here is capture all the steps we created and now either put them into our editor as comments or write them as psuedo-code that we can translate to real code.
By doing this, we can know exactly what the structure of the code we are going to write is going to look like which makes the job of filling in the actual code later trivial.
Let’s look at some psudeo-code for reversing a string.
// NewWord = “”
// Loop backwards through word to reverse
// NewWord += CurrentLetter
// Return NewWord
Pretty simple, but the key thing we have done here is outlined the structure of the code we will write to solve the problem.
Replace comments with real code
This step should be extremely easy at this point. If you have done all the other steps, this step involves no problem solving at all.
All we do here is take each comment and convert it into a real line of code.
Taking the string reversal, we might end up with something like this.
1 for 1 translation of the comments we created above for real code.
If you struggle here, there are usually two possible reasons:
- You didn’t break down the problem into small enough steps
- You don’t know your programming language well enough to do the conversion
If you didn’t break the problem down enough, try going back to the second step and being as meticulous as possible. Write out each and every single step. I know it is a pain, but do it, believe me it will be worth the effort.
If you don’t know your programming language well enough to do the translation, you may need to brush up here on some basic constructs. Any language you expect to be able to solve algorithm type problems in, you should know how to do the following things:
- Create a list
- Sort a list or array
- Create a map or dictionary
- Loop through a list, or dictionary
- Parse strings
- Convert from string to int, int to string, etc
If you don’t know how to do all of these things. Stop what you are doing now and learn them. It’s not a very long list, and the benefits will be profound.
Optimize the real code
Sometimes this step isn’t necessary, but it’s worth taking a look at your code and figuring out if you can cut out a few lines or do something simpler.
This is also a good place to make sure all your variables are named with long meaningful names. I cannot stress enough how important having good names for your variables and methods is for helping the person evaluating your code to understand what you were trying to do. This is especially important when you make a mistake!
I won’t give an optimization for our trivial example of a string reversal, but a word of advice here is not to get too tricky. Just try to mainly simplify your code and get rid of duplication.
A few final tips
If you follow this template for solving algorithm type problem, you should do very well in programming interviews, but the key to doing so is having confidence in this process.
The only way you are going to have confidence in this process is to practice it. It takes a good amount of faith to believe that spending 70% of your 30 minutes to solve a problem just thinking about the problem and not writing any code is the right approach, so make sure you have that faith when you need it.
I’ve talked about using TopCoder to become a better programmer before, and I still recommend it. Codility.com is another great site I have recently been introduced to.
There is one important step I did not include in the outline above, because I didn’t want to make the process any more complicated than it needed to be.
Many times you will find that a problem itself involves multiple large steps or is very complicated. In those instances, you will want to try and find a way to cut the problem directly in half and then following the process above for each half.
This method of tackling a problem is called “divide and conquer” and is quite effective. A good way to know where to break a problem in half is to think about what part of the problem if already given to you would make solving the rest easy.
The programming interview is merely one battle in a larger war: marketing yourself. For the full lowdown, take a look at my course: How to Market Yourself as a Software Developer.