Coding Interviews: Solving the “Staircase with N Steps” Problem

Photo by Jake Hills on Unsplash

A General Note about Coding Interviews

Coding interviews are very analogous to taking the SAT or GRE; sometimes they aren’t necessarily the best reflection of how you’ll perform at your job or in college, but more of a reflection of your preparation and resources.

As long as companies still use these types of problems, you’ll need to prepare for them.

Problem Source / Inspiration

https://www.dailycodingproblem.com
Asked by: Amazon

Problem Description

There’s a staircase with N steps, and you can climb 1 or 2 steps at a time. Given N, write a function that returns the number of unique ways you can climb the staircase. The order of the steps matters.

For example, if N is 4, then there are 5 unique ways:

• 1, 1, 1, 1
• 2, 1, 1
• 1, 2, 1
• 1, 1, 2
• 2, 2

What if, instead of being able to climb 1 or 2 steps at a time, you could climb any number from a set of positive integers X? For example, if X = {1, 3, 5}, you could climb 1, 3, or 5 steps at a time. Generalize your function to take in X.

Problem Solution

These problems can sometimes be hard to conceptualize, especially when using recursion. So with that in mind, I decided to illustrate the initial part of the problem below for n = 4.

A tree diagram of all possible step permutations for 4 total steps and a maximum step size of 2

As you can see from above, to solve this problem (without being a mathematician) we can visualize it as a tree-like structure and traverse it to find the branches that satisfy our criteria. I didn’t show all of the failed branches, but you could imagine a branch like 1–2–2 that would fail our criteria of taking exactly 4 steps.

Solution Part #1

Let’s break down the solution to the first part of the problem.

A recursive solution with step sizes of only 1 or 2

1. When we recurse, we are homing in on a criterion with each successive call of our function. In our problem, we are decrementing the number of total steps left by the step size that we took until there are no steps left.
2. Our recursive case can be seen on line 7. Here we’re invoking our function with n — 1 and n — 2, respectively. Then we sum the returned values of those subsequent calls.
3. We still have to handle the cases where we take too many steps. We handle this on lines 2 and 3 by returning 0 if n is negative (i.e. if we’ve taken too many steps).

Solution Part #2

Now let’s take a look at the more complicated scenario.

1. In this case, we’re now expecting an array of valid step sizes. Since we don’t know the step sizes ahead of time, we can’t hardcode our step size reduction like before.
2. Instead, we’ll iterate through the stepSizes array, apply our recursion criteria, and then return the sum of the values we produce. To do this, we’ll use Array.prototype.reduce because it allows us to declaratively iterate over an array and accumulate a value.
3. Our cases are similar to that in Part #1. We handle the cases where we take too many steps on lines 3 and 4, we have our base case on lines 5 and 6, and we handle our recursive case on lines 7 and 8.
4. In the recursive case, we invoke our function again with a remaining number of steps equal to n — stepSize. We then add the returned value of the function call to our sum variable.

Conclusion

These problem solutions aren’t very verbose; we were able to solve the more complicated part of this problem in 11 easy-to-read lines. The main challenge is to identify the problem as one where you could traverse all possible paths and determine whether each one satisfies the criteria.