Amazon Interview Question Software Engineer / Developers
Country: -
Interview Type: Phone Interview
f(0) = 0
f(1) = 1
f(2) = 2
for n >= 3
f(n) = f(n-1) + f(n-2) + f(n-3)
// The last step is 1, 2, 3, so three disjoint set
should not it be
F(1) = 1
F(2) = 2
F(3) = 4
F(n) = F(n-1) + 2*F(n-2) + 4*F(n-3)n ????
Or am i getting the question wrong
Please explain why is f(3)=4 and why do we need f(0)?
Won't f(3) be 3..
1) All 3 steps at a time
2) 2 at a time and then 1 last
3) each step at a time
Are we taking permutations of 2nd possibility? (1 step first and 2 later?)
Isn't this enough?
If n<3
F(1) = 1
F(2) = 2
F(3) = 3
and for n>=3
F(n) = F(n-2) + F(n-1)
#include<iostream>
#include<stdio.h>
using namespace std;
static int total = 0;
int level = 40;
void steps(int totalstepstillnow)
{
//printf("step = %d, totalstepstillnow = %d, \n",step,totalstepstillnow);
if(totalstepstillnow == level)
{
//cout<<"Reached !\n";
total++;
return;
}
if(totalstepstillnow > level)
{
return;
}
steps(totalstepstillnow+1);
steps(totalstepstillnow+2);
steps(totalstepstillnow+3);
}
int main()
{
steps(0);
cout<<total<<endl;
}
Solution in the CCI book is as below.
class CountingSteps {
public int countWaysRecursive(int n) {
if (n < 0) {
return 0;
} else if (n == 0) {
return 1;
} else {
return countWaysRecursive(n - 1) + countWaysRecursive(n - 2)
+ countWaysRecursive(n - 3);
}
}
}
Here F(0) == 1. If there are 0 steps then there are no ways to climb it. Is that correct ? Why is the code look incorrect but is still correct ?
There is exactly 1 way to climb 0 stairs. If anything is confusing here, it might be our informal notion, when using human language, of what constitutes a "way" to do something. We can make this notion precise: the number of ways to climb N steps with step sizes of 1, 2, and 3 is the number of distinct sequences consisting of 1, 2, and 3 whose elements sum up to exactly N. There is precisely 1 such sequence when N=0: the empty sequence.
That said, this recursive implementation has exponential complexity because it does not memorize answers to previously-solved subproblems. It can be augmented with dynamic programming to give a linear-time algorithm (though the simplest solution is still to solve it iteratively).
As i did not understand how can F(0) be 1 using above solution. Below is a revised one.
class CountingStepsAlternate {
public int countWaysRecursive(int n) {
if (n <= 0) {
return 0;
} else if (n == 1) {
return 1;
} else if (n == 2) {
return 2;
} else if (n == 3) {
return 4;
} else {
return countWaysRecursive(n - 1) + countWaysRecursive(n - 2)
+ countWaysRecursive(n - 3);
}
}
}
Output:
#1 Above) 1 1 2 4 7 13 24 44 81 149
#2 Alternate) 0 1 2 4 7 13 24 44 81 149
They differ at F(0) and i assume alternate solution is correct.
class CoutintStepsDP {
public int countWaysRecursive(int n, int[] cache) {
if (n <= 0) {
return 0;
} else if (n == 1) {
return 1;
} else if (n == 2) {
return 2;
} else if (n == 3) {
return 4;
} else if (cache[n] != -1) {
return cache[n];
} else {
cache[n] = countWaysRecursive(n - 1, cache)
+ countWaysRecursive(n - 2, cache)
+ countWaysRecursive(n - 3, cache);
return cache[n];
}
}
}
Input Steps: 0 1 2 3 4 5 6 7 8 9
Runs
Solution #1: 1 1 2 4 7 13 24 44 81 149
Solution #2: 0 1 2 4 7 13 24 44 81 149
Solution #3: 0 1 2 4 7 13 24 44 81 149
public class Problem1 {
public static void main(String[] args) {
CountingSteps c = new CountingSteps();
for (int i = 0; i < 10; i++) {
System.out.printf("%5d", c.countWaysRecursive(i));
}
System.out.println();
CountingStepsAlternate cA = new CountingStepsAlternate();
for (int i = 0; i < 10; i++) {
System.out.printf("%5d", cA.countWaysRecursive(i));
}
System.out.println();
CoutintStepsDP cDP = new CoutintStepsDP();
int cache[] = { -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
-1 };
for (int i = 0; i < 10; i++) {
System.out.printf("%5d", cDP.countWaysRecursive(i, cache));
}
}
}
/**
* # of Steps: 0 1 2 3 4 5 6 7 8
* 9 <br/>
* # of Ways : 1 1 2 4 7 13 24 44 81 149 81
*
*/
class CountingSteps {
public int countWaysRecursive(int n) {
if (n < 0) {
return 0;
} else if (n == 0) {
return 1;
} else {
return countWaysRecursive(n - 1) + countWaysRecursive(n - 2)
+ countWaysRecursive(n - 3);
}
}
}
class CountingStepsAlternate {
public int countWaysRecursive(int n) {
if (n <= 0) {
return 0;
} else if (n == 1) {
return 1;
} else if (n == 2) {
return 2;
} else if (n == 3) {
return 4;
} else {
return countWaysRecursive(n - 1) + countWaysRecursive(n - 2)
+ countWaysRecursive(n - 3);
}
}
}
class CoutintStepsDP {
public int countWaysRecursive(int n, int[] cache) {
if (n <= 0) {
return 0;
} else if (n == 1) {
return 1;
} else if (n == 2) {
return 2;
} else if (n == 3) {
return 4;
} else if (cache[n] != -1) {
return cache[n];
} else {
cache[n] = countWaysRecursive(n - 1, cache)
+ countWaysRecursive(n - 2, cache)
+ countWaysRecursive(n - 3, cache);
return cache[n];
}
}
}
bottom up approach
int waysnsteps(int n) {
vector<int> cache(n+1, 0);
cache[0]=0;
cache[1]=1;
cache[2]=2;
cache[3]=4;
int i=4;
while (i<=n) {
cache[i]=cache[i-1]+cache[i-2]+cache[i-3];
i++;
}
return cache[n];
}
steps 0 no of ways 0
steps 1 no of ways 1
steps 2 no of ways 2
steps 3 no of ways 4
steps 4 no of ways 7
steps 5 no of ways 13
steps 6 no of ways 24
steps 7 no of ways 44
steps 8 no of ways 81
steps 9 no of ways 149
steps 10 no of ways 274
F(1) = 1
- eugene.yarovoi October 23, 2011F(2) = 2
F(3) = 4
F(n) = F(n-1) + F(n-2) + F(n-3)