Interview Questions - Software Developer - Part 2

Problem

======

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.

Solution:

======

Recursive approach
==============

public int numSteps(int n){

           if(n==0 || n==1) {return 1;}

           else{

                  numSteps(n -1) + numSteps(n-2); 

          }   

}

if X = [I, 3, 5] 

             => numSteps(n-1) + numSteps(n-3) + numSteps(n-5);

Dynamic programming

================

public int numSteps(int n){

        int res;

       int[] nList = new int[n+1];

       nList[0] = 1; nList[1] =1; 

         if(n==0 || n==1) {return 1;}

           else{

                  for(int I=2; i<n;i++){

                     nList[I] = nList[I-1] + nList[I-2]; 

                   } 

              return nList[I];

          } 

}