# Part I: An interview gone horribly wrong

(If you hate tech satire, skip to Part II)

You’re sitting in a cramped room with a glass door in $TRENDY_CO’s headquarters. It’s the final interview of the day, your last chance to make a case that you deserve the job.

A mid-20s tech-bro wearing a $TRENDY_CO t-shirt, who you assume to be the interviewer, enters the room. You exchange pleasantries. The interviewer steals glances at your resume (probably the first time he’s seen it). A few minutes later, he announces that it’s time to “start off with some technical questions.” You nod in solemn agreement: After all, this is what you signed up for.

The interviewer proceeds with the first question. “You’re given a pointer to the root node of the **tree**…”

As soon as you hear “tree”, a word pops into your head.

“Recursion.”

You keep thinking to yourself, “I NEED TO USE RECURSION” to the point that you forget the interviewer is speaking.

Once you catch yourself drifting off, you ask the interviewer to repeat the question.

“You’re given a pointer to the root node of a binary tree. I want you to write an algorithm to invert the binary tree, so the left child of a node is now the right child, and vice versa.”

OK… so you think you can solve the problem using recursion. Now what?

No algorithm immediately comes to mind, so you try to draw inspiration from other recursive problems. A few classic textbook recursion problems come to mind: in-order traversal, towers of Hanoi, n-queens.

The only problem is that you don’t really know how those work. After all, who really pays attention in their algorithms class?

Your blood pressure and heart rate start to rise.

When the interviewer asks you what you’re thinking, you start stammering and offering drawn out “uhhhhs.”

Now your mind is in full panic mode, and your vision starts to blur.

In desperation, you take a whiteboard marker and start writing some (nonsensical) code while muttering to yourself about base cases and recursive cases. The interviewer furrows his brows and loudly sighs, expecting this interview to be yet another waste of his time. Every second feels like an eternity of torment, as you watch your interview hopes go down in flames.

After an agonizing 25 minutes, the interviewer decides to take mercy on you and ends the technical portion of the interview early. He asks if you have any questions about the company to which you respond with generic questions about the culture and work-life balance at $TRENDY_CO.

Once the interview concludes, you make a beeline for $TRENDY_CO’s exits. You’re so mortified of your interview that you can’t make eye contact with anyone for the rest of the day. Later that night, you go on Hacker News to read posts ranting about the sad state of affairs in tech interviewing (maybe even leaving a comment or two yourself).

#### Exhibit A:

Google: 90% of our engineers use the software you wrote (Homebrew), but you can’t invert a binary tree on a whiteboard so fuck off.

— Max Howell (@mxcl) June 10, 2015

(If you’re reading this Max, I love homebrew)

No one wants to go through a bad interview. It’s embarrassing. However, the good news is that no one else will remember it: Bombing an interview won’t affect your future job prospects. There’s no subreddit for interviewers to blacklist people who performed poorly in a technical interview.

It’s a poorly kept secret that tech interviews are inherently random. Maybe you happened to study the exact problems that the interviewer asks. Or maybe the interviewer asks a question about topological sorting, and you’ve never heard of that phrase before.

While you can’t take the randomness out of the interviews, you can learn a set of techniques to minimize the number of surprises you find in an interview.

# Part II: Your guide to overcoming your worst (interview-related) fear

Personally, my top three fears are:

- Being trapped in small places
- Awkward conversations
- Not being able to solve a problem in an interview

If you’ve ever had a bad interview, you’ll understand why fear #3 ranks so highly. My goal for the rest of the post is to prepare you so that interviewing is no longer in your top three list of fears. After this guide you can let something else, like clowns, take its place.

By the end of this post, you will know how to approach recursion problem, lower your blood pressure during interview, and become a better lover (maybe not the last one, unless your significant other **loves** recursion).

## What is recursion?

Recursion is when something is defined in terms of itself. Some people like to talk about Fibonacci sequences or binary trees, but I’ll keep it simple.

An example of recursion in your daily life are the folders you use to organize stuff on your computer. A folder has a name (e.g. “Desktop”) and can contain files or even more folders. It may be strange to think about recursion in the abstract, but folders containing folders makes a lot of sense.

## What is a recursion problem?

The general rule of thumb is that “recursion problems” refer to problems that are easier to solve using recursion. There isn’t a hard-and-fast rule since many problems can be solved recursively or iteratively (but one approach could be much simpler).

For example, suppose you want to find a photo in your *Photos* folder, but you don’t know when you took it. One way to find the photo is to go into the *05-May* folder and check all of the photos in that folder. That means if *05-May* contains more folders, check those folders too, and so on. In this case, you would also check the *Graduation* folder.

If you don’t find the photo anywhere in *05-May*, you can check *04-April*, *03-March*, etc. until you find the photo or until you have exhaustively looked at every photo in *Photos*.

If you’re familiar with graph traversal algorithms, this is depth-first search. This search algorithm is natural to write using recursion and hard to write iteratively using for/while loops without additional data structures.

## How do I know when to use recursion?

Here are some guidelines to know when you should consider using recursion.

- When you want to “try” every possibility. For example, if the problem is to generate all permutations, visit every node in a graph, etc.
- When the object is defined recursively. Trees or graphs are good examples.
**When it’s hard to solve the problem in any other way**. This guideline will probably be the most useful. Think about how to solve the problem using a for/while loop. If it seems like you’d have to use multiple nested for loops or you can’t think of a way to do it at all, consider using recursion.

This list is by no means exhaustive, because choosing to solve a problem recursively is a judgment call that you’ll have to make. As you do more recursion problems, you’ll get a better sense of whether a recursive or iterative approach is simpler.

## How do I solve a recursion problem?

At a high level, there are two parts of a recursive problem: the base case and the recursive case. The recursive case tells the program how to break a problem down into a simpler one, and the base case tells the program how to solve the problem once you can’t break it down anymore.

To illustrate how we can solve a recursive problem, we will work through the following problem:

Given an array of integers, return the set of all permutations

### 0. Clarify the problem

If you don’t think you have any clarifying questions to ask at all, think harder. Before you solve a problem, you want to be absolutely certain that you know exactly what you’re solving.

One way to generate questions is to start working through small examples and asking if the answer you expect agrees with the interviewer.

Take a minute to think about what you would ask about this problem.

Here’s what I would ask:

- How do you define a permutation? One way you can word this is, “If I understand correctly, a permutation is an ordering of the elements in the array.”
- As a follow up to that question, I would ask if all of the elements in the array are unique. If they are not unique, how should we treat them? This question is important because it will affect how you solve the problem (See below).

For the purposes of this problem, assume every element in the array is unique.

### 1. Find the easy way out: solve the base case

Thinking about how to solve the general recursive problem can be difficult. Instead, you can try to simplify the problem to get some intuition and then use the simplified problem to guide your solution.

The question you should **always** ask yourself is: What are the simplest examples you can think of?

For this problem, there are two such examples:

- When the array is empty.
- When the array has one element.

In both cases, there is only one ordering for the array, which is the array itself. This means that, when someone tells you to find the permutations of an array with no more than one element, the set of permutations will contain only the passed-in array.

Figuring out the base case is important because it’s defines when the program finally terminates. If you don’t define the base case properly, your program will run forever.

### 2a. Pretend someone did (almost) all the work for your: solve the recursive case

*Note: 2a and 2b both find the recursive case, but* *do** so using two different approaches*

This approach is typically called “top-down” recursion. Your goal is to find a way to break the problem into an easier problem to solve that you can then pass off to another function call.

Suppose you want to find all of the permutations for the array *[1, 2, 3]*. You can assume that someone gave you a *magical* function that will generate all permutations for arrays of size two or smaller. How can you use this function to solve the problem for the original array of length three?

You can take the last element (3) out of the array, which leaves you with an array of two elements, *1* and *2*. In each permutation, there are three places to put the element *3*: The front, the middle, and the end. Once you choose where 3 will go, you just need to figure out the different ways of ordering the remaining two elements.

Well, someone gave you this *magical* function that generates the permutations for arrays of size two or less. Why don’t you use that on the array *[1, 2]*? You can then substitute the question marks with the permutations of the smaller array *[1, 2]*.

Repeat this step for each position you can place 3, and you will get the full set of permutations.

Now you might be wondering where this*magical*function came from. Well, this magical function is the

**function you’re writing**. That’s the beauty of recursion.

You specified a way to break the problem down (by taking out one element, generating permutations for the smaller array, and then combining those two) and also specified when the program should stop recursing (the base case). This is all you need to solve the problem.

When you make the recursive call to generate permutations for *[1, 2]*, the program will take out 2 and generate the permutations for *[1], *which is a base case. Recall that in the base case, the set of permutations contains only one array, which is *[1]*. Once the function returns from the base case, the program will put 2 in the front of *[1]*, and 2 in the back of *[1]*. This will generate the two permutations, *[2, 1]* and* [1, 2] *.

### 2b. Baby steps: solve the recursive case

This approach is typically called “bottom-up” recursion. You start with the base case that you can immediately solve and incrementally make the problem harder. Solving the incrementally harder questions in succession can often lead to an algorithm through pattern matching.

To see this in action, let’s apply this principle to our problem of generating permutations. Below is a base case. There is only one ordering of an array with one element.

Now, suppose you want to generate the permutations for an array with two elements, say, *[1, 2]*. The solution is still straightforward; either 1 or 2 is in the front, which means there are two permutations.

*[1, 2, 3]*. By now, you might have noticed the pattern. There are two permutations to the array

*[1, 2]*, which are

*[1, 2]*and

*[2, 1]*. To generate the set of permutations for

*[1, 2, 3]*, you can take the two permutations you generated for

*[1, 2]*and insert 3 into each position of those permutations.

More broadly, to generate the permutations for an array of size *n*, you can take the permutations of the first *n-1* elements of the array, and then insert the *n*th element into each position of each permutation.

### 2c. Summing up the recursive case

The two common ways of figuring out the recursive case are through using a “top-down” or “bottom-up” approach.

Top-down

- Define a way to break the problem down into a smaller one
- Assume you have a
*magical function*that will solve the smaller problem for you (which is really just the function you’re writing)

Bottom-up

- Start from the base case and solve incrementally harder problems
- Figure out how you can use an easier instantiation of the problem to solve the current, harder problem (Ex: using the permutations of
*[1, 2]*to generate the permutations of*[1, 2, 3]*)

As you can see above, both approaches gave (almost exactly the same) solutions for generating permutations. Which approach you use is often a matter of preference. Personally, I like top-down because I like magic.

### 3. How long does it take: analyze the runtime and space complexity

Analyzing the runtime of the approach above is kind of tricky because you can’t just count the number of recursive calls. In each call, you iterate through a list of permutations and create multiple strings from each permutation. I don’t expect an interviewer to ever ask you the specific runtime for this problem. However, you may be asked to say at least how long you would expect the function to run/at least how much space it’ll take.

One general technique is to think about how many elements you have to process. In this case, the problem you’re working on requires you to return all of the permutations. If the size of the array you return has size *O(# permutations)*, then your runtime complexity can’t be any faster, since you have to add *O(# permutations)* to your array. So, if I told you an array had *n* elements, how many permutations of those elements are there? (Answer: A lot.)

Let’s think about the number of permutations for a three element array. As you know from solving the recursive case above, there are six different orderings. One way to break the problem down is to think about how many different elements you can put in each position of the array.

For the first position, there are three numbers you can choose (1, 2, or 3).

For the second position, there are two numbers you can choose (If you chose 1 for the first position, then you can choose 2 or 3).

For the third position, there is one number you can choose (If you choose 1, 2 for your first two numbers, then the last one must be 3).

After replacing the underscores with the number of elements we can put in each position, you’re left with the following:

In total, there are *3 * 2 * 1 = 6* ways to order the 3 elements, which agrees with what you found in the recursive case. For a general array of length *n*, the number of permutations is *n*(n-1)*(n-1)*…*2*1*. The shorthand for this is *n!*, or *n* factorial.

So to answer our original question, there are *n!* different permutations, so your space and runtime complexity will be at least proportional to *n!*, which grows very quickly (For a 15 element array, there are over a trillion ways to order them).

### 4. Write the pseudocode

Explaining your approach using pseudocode will force you to organize your thoughts above into a cohesive algorithm. As an added benefit, the interviewer will have an easier time understanding your approach, which means they can give you hints if you’re going down the wrong path.

At this point, you may realize that your algorithm doesn’t work, sending you back to the drawing board. And that’s OK. That’s what this step is designed to do. Writing your approach in English is cheap, but writing code is expensive. For one, if you write half of your code only to realize that it doesn’t work, you’re screwed. Ideally, you want to do as much problem solving as possible before writing code; it’s easier to change approaches when you don’t have a piece of broken code staring back at you.

Take a moment to think about how you would write a step by step approach to solving this problem (without using code!). My pseudocode is below:

- Base case: If the array length is zero or one, then return an array containing only that list
- Recursive case:
- Take the last element out of the passed in array
- Generate all permutations for the array (which now has one fewer element)
- For each permutation, add the last element to each possible position to create a new permutation. Then add it to the list of permutations

### 5. Write the code

By the time you get to this point, you already finished the hardest part of the problem, which is figuring out the approach. The remainder is a matter of translating your approach into code.

Java solution

private static List<List<Integer>> generate_permutations(List<Integer> A) { List<List<Integer>> permutations = new ArrayList<>(); if (A.size() <= 1) { permutations.add(A); return permutations; } Integer first = A.get(A.size() - 1); List<Integer> remaining = A.subList(1); List<List<Integer>> result = generate_permutations(remaining); for (int i = 0; i < permutations.size(); i++) { for (int j = 0; j < A.size() j++) { List<Integer> copy = new ArrayList<>(permutations.get(i)); copy.insert(j, first); permutations.add(copy); } } }

Python solution

def generate_permutations(A): if len(A) <= 1: return [A] first = A[-1] result = generate_permutations(A[:-1]) permutations = [] for p in result: for i in range(len(A)): left = p[:i] right = p[i:] permutations.append(left + [first] + right) return permutations

## You’ve made it to the end of the guide!

Congrats! In this guide, you’ve learned a step-by-step approach to conquering recursion problems in interviews.

To recap, here are the steps to solving a recursion problem:

- Solve the base case by thinking of the simplest examples you can solve
- Solve the recursive case, either by using a top-down or bottom-up approach
- Analyze the runtime and space complexity
- Write the pseudocode
- Write the code

As you practice solving recursion problems, you’ll inevitably run into difficulties or get stuck. Here’s my advice to you:

**Problem solving is messy**and it won’t ever look as easy as it does in this post. Sometimes you’ll have to jump back and forth between steps.**Separate problem solving from writing code.**The worst thing you can do when you don’t know how to solve a problem is start writing code. Making an upfront investment in solving the problem will save you critical minutes in an interview.**Always work through examples by hand.**I don’t care if you’re the second coming of software engineering interview Jesus. Just do it.

# Your next challenge

- Solve one recursion problem this week using your guide. Let me know how it goes! Send an email to reggylong@gmail.com telling me what problem you solved.

## Leave a Reply