## Amazon Interview Question for Production Engineers

Team: kindle
Country: India
Interview Type: In-Person

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

F(n) = F(n-1) + F(n-2)
F(1) = 1
F(2) = 2

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

I think it is
F(n) = (1+F(n-1))+(1+F(n-2))
F(1) = 1
F(2) = 2

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

@sai: Nope. It's what I said it is. By my formula, there are 3 ways to go down 3 steps: (2, 1), (1, 2), and (1, 1, 1). By your formula, it would be 5 ways, which is clearly wrong.

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

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

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

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.

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

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

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

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

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

Just consider once fibonacci series for this problem.

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

``````Define "f (i) - # of paths of going from step i to ground"
f (1) = 1;
f (2) = 2;
f (n) = f (n - 1) + f (n - 2); // for n > 2

The computation is similar to fibonacci sequence.
We can achieve it in O(log (N)) for Nth step.

Notice:
[f(n) f(n - 1)] = [f(n-1) f(n - 2)] x [1 1]
[1 0]``````

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

@kartikaditya..........f(2) is also 1..and not 2

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

f(2) = 2, as from second step you can get down by either 1+1 steps or 2 steps at once, i.e total 2 paths

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

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

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

``````// to find the no of steps
static int noOfPaths(int sum){

if(sum == 0 || sum == 1) return 1;
if(sum == 2) return 2;
return noOfPaths(sum-1)+noOfPaths(sum-2);
}

will this work?``````

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

I think it is
F(n) = (1+F(n-1)) + (1+F(n-2))
F(1) = 1
F(2) = 2

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

F(n) = F(n-1) + F(n-2)
F(1) = 1
F(2) = 2
looks to work fine, but I am not getting why this is working? I mean how did you come to this answer, was it just by analyzing numbers or based on some other logic?

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

Isn't there just one path to get down ? There may be multiple ways but just one path.

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

private static int path(int[] a, int index, int sum, int n)
{
if (sum == n)
{
return 1;
}
if (sum > n)
return 0;

return path(a, index + 1, sum + 1, n) + path(a, index + 1, sum + 2, n);

}

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.