Amazon Interview Question
Production EngineersTeam: kindle
Country: India
Interview Type: In-Person
here is the solution which prints number of paths as well as each path.
at every step we have to choices either take 1 step or take 2 step.
#include <cstdlib>
#include <iostream>
using namespace std;
int path(int a[],int index,int sum,int n)
{
static int count=0;
if(sum==n)
{
cout<<"\n";
for(int i=0;i<index;i++)
cout<<a[i]<<" ";
count++;
return 0;
}
if(sum>n)
return 0;
for(int i=1;i<=2;i++)
{
a[index]=i;
path(a,index+1,sum+i,n);
}
return count;
}
int main(int argc, char *argv[])
{
int n=8;
int *a=new int[n];
cout<<"\nNumber of Paths :"<<path(a,0,0,n);
free(a);
system("PAUSE");
return EXIT_SUCCESS;
}
It is a binary tree. Each node you can take 1 step or two step. Construct the binary tree and the number of leaf nodes in the tree will be the number of possible paths.
try for 5
5
4 3
3 2 2 1
2 1
there are 5 leaf nodes
but the answer will be 8
here is the sanpshot of my output for 5
1 1 1 1 1
1 1 1 2
1 1 2 1
1 2 1 1
1 2 2
2 1 1 1
2 1 2
2 2 1
Number of Paths :8Press any key to continue . . .
if i m missing something
Yes, you are missing something. Leafs should be 1 or 0 (a value for each there is only one step left). For the leafs with 2 in your tree there are 2 ways of getting to the base - <1 1> and <2>
So for your tree each leaf with "2" should actually become a node with 2 leafs.
2+ 1 + 2 + 2 + 1 = 8
Rough sketch of the function is given below:
int find_no_of_paths(int n)
{
if(n==0 || n==1) {
path++;return;
} else if (n<0) {
return;
} else {
return (find_no_of_paths(n-1)+find_no_of_paths(n-2));
}
}
F(n) = F(n-1) + F(n-2)
- eugene.yarovoi December 18, 2011F(1) = 1
F(2) = 2