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, 2016int combinations(int n) { if(n<=1) return 1; if(n==2) return 2; if(n==3) return 3; int sn_3 = 1; int sn_2 = 2; int sn_1 = 3; int s = 0; for(int i=3; i<=n; i++) { s = sn_3 + sn_2 + sn_1; sn_3 = sn_2; sn_2 = sn_1; sn_1 = s; } } return s;