I signed up for Stanford’s online course, Algorithms: Design and Analysis Part 1, via Coursera. For those people with less traditional comp sci backgrounds, there are plenty of resources to get you up to speed. Lifehacker referenced a list of free, online courses, that would be the equivalent of a bachelor’s degree in computer science. I chose to start with algorithms. This seems to be the weakest point of self-taught programmers because you honestly rarely have to use it. It also happens to be one of the favorite type of problems interviewers like to ask.
I wanted to blog about the merge sort algorithms we’re learning in class or the problem sets I’m working on, but Coursera has a strict honor code that prevents me from facilitating other students from cheating. Instead, I’m going to talk about how to approach those dreaded interview questions that need to be dealt with using recursion. Most of the time, interviewers won’t even say they’re looking for recursion. They’ll just say something like, write me a method that outputs this. But if the output depends on the answer to a simpler instance of the input, you’ve got yourself a recursion question.
Here’s how to approach the problem:
Identify the input. It might be an array, string or number. Usually the problem will be framed something like, “Given a number
n… blah blah blah”. So
nis your input and you know it’s a number. You might want to ask the interviewer to clarify. Is
na positive integer or is it a float?
Identify how an simpler instance of the input would be helpful. If your input is an integer, the smaller instance of the problem could be
n - 1. If your input is an array, a simpler instance could be a subarray of the original array.
Identify the base case. The case where there does not exist a simpler instance of the input.
Write the method, using recursion. A recursive method calls itself with a simpler instance of the input.
Example Interview Question: Write a method that given the index
n, output the value in the Fibonacci sequence.
The Fibonacci sequence goes something like 1, 1, 2, 3, 5, 8,…
Step 1: The input is
n, a positive integer that represents an index.
Step 2: Any value in the Fibonacci sequence is the sum of the previous two values in the sequence. We need the output of
n - 1 and
n - 2 to calculate
Step 3: The base case is at index
n - 2 for both indexes would result in a negative number, which we know are invalid inputs.
Step 4: Use that recursion magic. Voila!
1 2 3 4 5 6 7
One of the reasons why recursion is difficult to understand is our inability to follow how many times the method calls itself till it gets to the base case, then bubbles back up. Seeing a recursive method can leave us questioning, does this really work? I find that starting with a couple steps above the base case will usually help validate the method works. Then, like the comic above, I cross my fingers.