## Linkedin Interview Question

Software Engineers**Country:**United States

**Interview Type:**In-Person

I think ChrisK did a mistake this time, a rarity.

Suppose there are K options, then 3^K is correct.

But if the steps taken are n, then 3^n is wrong, why? Because set n = 1.

Clearly one can make only 1 step, 1 way.

If n = 2, then one can make 1 + 1 or 2, so 2 ways.

If n = 3, then one can make 1 + 1, 2 + 1, 1 + 2, 3 -> 4 ways.

Thus, the pattern is :

n < 1 : 1

n = 1 : 1

n = 2 : 2

n = 3 : 4

...

Giving: ( it is a rip off of Generalized Fibonacci like sequences )

S(n) = S(n-1) + S(n-2) + S(n-3)

=====

S(3) = S(2) + S(1) + S(0) = 4

S(4) = S(3) + S(2) + S(1) = 4 + 2 + 1 = 7

=== is it correct? Let's verify ? ====

1 + 1 + 1 + 1

1+1 + 2

1+ 2 + 1

2 + 1 + 1

2 + 2

1 + 3

3 + 1

===> Yess! ( or I am totally wrong? )

```
// ZoomBA let's you use sequences
steps = seq( 1,1,2 ) -> { $.p[-1] + $.p[-2] + $.p[-3] }
n = 5
total = fold ( [3:n+1] ) -> { steps.next }
println( total )
```

So here is my solution, it uses javascript though, it uses ES6 (for spread operating on array, default parameters, this will run fine in current versions of Firefox, I did this in Firefox 50):

```
function getHopPathsCnt(totalsteps, maxhopability, curstep = 0, taken = [], total={count:0}) {
if (totalsteps === curstep) {
total.count++;
console.log('A possible hop path:', taken.join(' '));
} else {
for (let hopped = 1; hopped <= maxhopability; hopped++) {
if (totalsteps - curstep >= hopped)
getHopPathsCnt(totalsteps, maxhopability, curstep + hopped, [...taken, hopped], total);
}
}
if (curstep === 0) {
console.error('Total ways to climb', totalsteps, 'steps with up to', maxhopability, 'hops at a time:', total.count);
return total.count;
}
}
```

To use it:

getHopPathsCnt(3, 3);

Outputs:

```
> A possible hop path: 1 1 1
> A possible hop path: 1 2
> A possible hop path: 2 1
> A possible hop path: 3
> Total ways to climb 3 steps with up to 3 hops at a time: 4
> 4
```

Its just like coin change problem.

```
package dp;
import java.util.Arrays;
public class NSteps {
public static void main(String[] args) {
int[] possibleSteps = {1,2,3};
long startTime = System.nanoTime();
System.out.println(getNumberForSteps(possibleSteps, 30));
long stopTime = System.nanoTime();
System.out.println("Time taken: " + (stopTime - startTime));
startTime = System.nanoTime();
dpSolution(possibleSteps, 30);
stopTime = System.nanoTime();
System.out.println("Time taken2: " + (stopTime - startTime));
}
public static int getNumberForSteps(int[] steps, int n){
if (n == 0) return 1;
if (n < 0) return 0;
return getNumberForSteps(steps, n-steps[0]) + getNumberForSteps(steps, n-steps[1]) + getNumberForSteps(steps, n-steps[2]);
}
public static void dpSolution(int[] steps, int n){
int[] arr = new int[n+1];
arr[0] = 0;
for(int i=1; i <arr.length; i++){
for(int step: steps){
if(i-step == 0){
arr[i] += 1;
}else if(i-step < 0){
continue;
}else{
// i - step > 0
arr[i] += arr[i-step];
}
}
}
System.out.println(Arrays.toString(arr));
System.out.println(arr[n]);
}
}
```

Building on ChrisK solution..

```
import java.util.*;
public class StepCount {
public static void main(String args[]){
Scanner scn = new Scanner(System.in);
System.out.println("Enter the total number of steps to climb: ");
int numSteps = scn.nextInt();
int [] stepArr = new int[numSteps+1];
for(int i=0;i<stepArr.length;i++){
stepArr[i]=-1;
}
System.out.println("The total number of ways the child can climb "+numSteps+" is "+findWays(numSteps,stepArr));
}
/* Below method finds the number of possible ways to climb numSteps within the constraints using memoized
recursion. The child can reach the last step either by hopping 1, 2 or 3 steps. So the total number of
ways for achieving this is sum of the total number of ways to reach numSteps-1, numSteps-2 and numSteps-3.
*/
public static int findWays(int stepCount, int[] memArr){
if(stepCount<0) return 0;
else if(stepCount==0) return 1;
if(memArr[stepCount]>-1) return memArr[stepCount];
else{
memArr[stepCount] = findWays(stepCount-1,memArr)+findWays(stepCount-2,memArr)
+findWays(stepCount-3,memArr);
return memArr[stepCount];
}
}
}
```

oops ;-) NoOne is right, here my update, maybe it helps

to understand the recursion although everything has already been

said by NoOne that's worthwhile.

Recap of question:

- it asks how many hop combinations are possible to go the distance of n steps

- a hop can be either 1,2 or 3 steps

- hoping 2-1 is not the same as 1-2

therefore we can express is recursively:

S(n) = S(n-1) + S(n-2) + S(n-3)

I thought of it as follows, let S(n) be the # of combinations

to go n steps

a) to go n+3 is the S(n+2) + the hop with distance 1

b) to go n+3 is the S(n+1) + the hop with distance 2

c) to go n+3 is the S(n) + the hop with distance 3

d) S(n+3) = S(n) + S(n+1) + S(n+2)

<=> S(n) = S(n-3) + S(n-2) + S(n-1)

it can be computed recursively if you memoize in O(n), otherwise

big-O of S < big-O of T(n) = 3*T(n-1) = O(3^n) (closer bound

is possible with the master theorem or a more complex prove)

iterative computation will be something like Fibonacci:

- Chris December 11, 2016