[Challenge] Stairmaster 📶

challenge

#1

Code Challenge #19: August 16, 2017

Every week, we feature the type of brain-teasing question that might be asked in a full-stack 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 follow-up 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 of n steps, taking 1, 2, or 3 steps at a time. Write stairmasterN 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 of n steps, taking x,y, …, z steps at a time. Write ultimateStairmaster 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:


Essential Information on Code Challenges
#2

The Challenge

class StairCases20{
    public static long stairCase20(long n){
       long check=0;
        long a=0,b=1,c=1;
        for(int i=0; i<n-1; i++){
            check=a+b+c;
            a=b;
            b=c;
            c=check;
        }
        return check;
    }
    public static void main(String s[]){
        System.out.println(stairCase20(20));
    }
}

import java.util.*;
class StairCase{
    public static long stairCaseN(long n){
       long sum=0;
        long a=0,b=1,c=1;
        for(int i=0; i<n-1; i++){
            sum=a+b+c;
            a=b;
            b=c;
            c=sum;
        }
        return sum;
    }
    public static void main(String s[]){
        Scanner sc=new Scanner(System.in);
        System.out.println(stairCaseN(sc.nextInt()));
    }
}


Check this out https://repl.it/KM3U/8

_In this program I applied fibonacci approach because if we consider the variation or flow of program it is best according to me!

For example:-

if we have four steps so how many ways are better to climb, The skipping problem but with restriction of (1,2,3). So I applied last case to calculate the total number of ways.

So it is fibonacci series (print last number last element of series) with predefined three initial values (0,1,1) and then keep adding and shift values to find next number until and unless loop 2 gets stopped at N-1_


#3

I have a question. For the second argument on hard difficulty, will it contain all positive integers up to the max() ‘[1,2,3,4,5,6]’? Or can it have an input like ‘[3, 6, 2, 4]’?


#4

Python 3 code for this challenge is given below. Full explanation can be found via the link.

https://repl.it/KRv1/3

def ultimateStairmaster (n,stepSize):
  step = [0 for x in range(0,n+1)]
  m =len (stepSize)
  step [0]=1  #This is required to increment the number of permuations by 1 if the step size is equal to the number of steps being evaluated.
  
  for i in range (1,n+1):#iterate through step counts
    for j in range(0,m):#iterate through all step sizes defined by user
      if stepSize [j] <=i:
        step[i]+=step[i-stepSize[j]]
  return step [n]
  
S =[3,1,2]
print (ultimateStairmaster(20,S))

#5

The input can be randomised, but you can assume all integers will be above 0.


#6

Javascript Answer to Hard Difficulty. I presume not the most efficient way since it’s brute force, but thought I would post anyways. Need to brush up on my combinatorial math skills…

Repl.it link:

function ultimateStairmaster(n,steps) {
  //set up an array queue that will hold all possible arrays until at or over determined number of stairs
  var theArrays = [];
  var count = 0;
  //cycle through the array of arrays, adding all possibilities then judging whether they remain in queue, reach the determined number of stairs or overshoot
  do {
    var tempArray = theArrays.shift();
    //pop off the first array from queue and cycle through the possible step amounts, adding the new array back to the queue if not yet at or over number of stairs to climb
    for (var j = 0; j<steps.length; j++) {
      var testArray = Object.assign([],tempArray);
      testArray.push(steps[j]);
      var newSum = testArray.reduce(function(a,b) {return a+b;}, 0);
      if (newSum<n) {
        theArrays.push(testArray);
      } else if (newSum==n) {
        count++;
      };
    };
  } while (theArrays.length > 0);
  return count;
}

#7

Hi everyone!
There’s my participation for this challenge. I tried to put enough explanations in the source code. I’m not a native english speaker, so please be gentle :slight_smile:

To run this program, you just have to click run and type main()


#8

Hi this challenge is now over.

There has been some great submissions considering this was quite a hard technical challenge.

For some beautifully simple really elegant Python the winner is @sirrobsmith.

Well done to everyone who took part! Look out for a new challenge tomorrow.