## Amazon Interview Question

Production Engineers**Team:**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