## Linkedin Interview Question for Software Engineers

Country: United States
Interview Type: In-Person

Comment hidden because of low score. Click to expand.
2
of 2 vote

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:

``````int 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;``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

what are the total number of possible combination?
- is 1-2-3 equal 2-1-3? (does order matter?)
- is 3-3-1 equal 3-2-2? (same distance?)

there are 3^n combination if order matters

Comment hidden because of low score. Click to expand.
0
of 2 vote

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 )``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

Hi ChrisK, yes in the interview they said order matters.

Comment hidden because of low score. Click to expand.
0
of 0 vote

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);
}
}``````

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``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````def count_comb(n):
if n < 0:
return 0

if n == 0:
return 1

return count_comb(n-1) + count_comb(n-2) + count_comb(n-3)``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

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]);
}

}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

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];

}

}
}``````

Comment hidden because of low score. Click to expand.
-2
of 2 vote

The possible combination at n steps can be calculated from the following function;

f(n) = f(n-1) + f(n-2) * 2 + f(n-3) * 4

1 more step can be done by only one way (1)
2 more steps can be done by 2 ways (2, 1 + 1)
3 more steps can be done by 4 ways (1 + 1 + 1, 1 + 2, 2 + 1, 3)

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.