## Amazon Interview Question for SDE1s

• 0

Country: India
Interview Type: In-Person

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

The problem doesn't specify if it can go leftward or upward.

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

``````public static int countPath(int m, int n) {
int [] [] count = new int[m][n];
for(int i=0;i<m;i++) {
for(int j=0;j<n;j++) {
if (i == 0 || j == 0)
count[i][j] = 1;
else
count[i][j] = count[i-1][j]+count[i][j-1]+count[i-1][j-1];
}
}
return count[m-1][n-1];
}``````

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

If all cells are accessible (which is what your code assume), there is no need for all this...

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

Can you provide a better solution ?

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

Every path has (m-1) downward sections and (n-1) rightward sections.

But in total (m-1) + (n-1) = m+n-2 sections

Answer is (m+n-2) choose {either (m-1) or (n-1) doesn't matter}

Why? Because we are counting the number of ways to build a path (i.e., choosing positions for downward paths and filling rest as rightward OR vice versa).

"choose" binomial coefficient can be found using dinamic programming using Pascal's identity and methods similar to Fibonacci sequences' code.

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

for the line count[i][j] = count[i-1][j]+count[i][j-1]+count[i-1][j-1]; there are some bugs in it. It should be count[i][j] = countPath(i-1, j)+countPath(i,j-1)+countPath(i-1, j-1);

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

never mind i thought it worng sorry

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

0 or infinite given the question.

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.