Code Challenge #19: August 16, 2017
Every week, we feature the type of brainteasing question that might be asked in a fullstack developer’s job interview at places such as Google and Facebook.
This week’s challenge was reported to have been asked in interviews at Facebook:
The Challenge
Write a function,
stairmaster20
, that will compute the number of ways to climb a flight of 20 steps, taking 1, 2, or 3 steps at a time.

Function Name:
stairmaster20
 Input: none
 Output: a positive integer representing the number of ways you can climb the flight of 20 stairs by climbing 1, 2, or 3 steps at a time.

Example: say this problem were framed around climbing 4 steps – in this case
stairmaster4 => 7
, as there are seven different ways one can climb four stairs using a combination of climbing 1, 2, or 3 steps at a time are([1,1,1,1] [2,1,1] [1,2,1] [1,1,2] [2,2] [1,3] [3,1])
 In this challenge we are looking for a permutation, not a combination, as the order matters – climbing one step then two steps is different from climbing two steps then one step.
 What if your interviewer had followup questions, for example changing the number of floors to 50? What if you could now jump four steps at a time? Try to write your code so that it is easily read, easily maintained, and can be adapted to modifications in the interviewer’s questioning.
 Always remember to explain your code and the thought processes behind it!
Find out more about basic challenges.
Intermediate Difficulty
Write a function,
stairmasterN
, that will compute the number of ways to climb a flight ofn
steps, taking 1, 2, or 3 steps at a time. WritestairmasterN
as efficiently as possible.

Function Name:
stairmasterN

Input:
n
– any positive integer 
Output: a positive integer representing the number of ways you can climb a flight of
n
stairs by climbing 1, 2, or 3 steps at a time. 
Example:
stairmasterN(4) => 7
 Don’t forget to explain your submission just as you would do in a job interview setting!
Find out more about intermediate challenges.
Hard Difficulty
Write a function,
ultimateStairmaster
, that will compute the number of ways to climb a flight ofn
steps, taking x,y, …, z steps at a time. WriteultimateStairmaster
as efficiently as possible.

Function Name:
ultimateStairmaster

Input:
n
– any positive integer,[x,y,.....,z]
 an array of integers, not necessarily in order, that has at least one number in but doesn’t have an upper limit. 
Output: a positive integer representing the number of ways you can climb a flight of
n
stairs by climbing [x,y, …,z] steps at a time. 
Example:
ultimateStairmaster(4, [1,2,3,4]) => 8
 Don’t forget to explain your submission just as you would do in a job interview setting!
Find out more about hard challenges and Big O
Reply
to this thread with a link to your code on repl.it and paste your properly formatted code to participate! Don’t just submit your code, remember to explain
your solution, too! If you want to be considered as the winner, your function must
have the correct name
and provide output in the format specified
above, you also need to abide by our other simple rules.
As always solutions using imports to do all the heavy lifting such as itertools
will not be considered for the winner.
When including your repl.it link, please just give us the link and not the code preview! Just put a space before your URL so that the preview box doesn’t show – too many preview boxes can make the thread hard to read.
The fine print:
Click the links to find out more about:
 the rules & how to participate in challenges
 how challenges are used as job interview questions
 why Codecademy runs challenges (and why they are formatted this way)
 more details about the challenges and why we think they are useful.
 find previous challenges (and see the past winners) in our Challenge Index