## Interview Question for Applications Developers

Country: United States

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

If the paths can only go down or right then straightforward dynamic programming can be used to solve the problem. To reach (y,x) you have to either reach (y-1,x) or (y,x-1) immediately prior; so the number of paths for these two sub-problems are added together.

``````P(y, x) = P(y-1, x) + P(y, x-1)
P(0, x) = 1
P(y, 0) = 1``````

This can be done either bottom up (with a table), or top down (with memoization and recursion).

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

Can we deduce a direct numerical formula?

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

the formula is what @SK wrote below, i.e.: C(M + N, N) or C(M + N, M)

But apparently the problem is underdefined: it does not say that we can move only down and right. Otherwise, the number of ways is infinity ! (loops)

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

C(M + N, N) or C(M + N, M)

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

#include<stdio.h>
int count = 0;
void Recursion(int right, int down) {
if (right == 1 && down == 1) {
count++;
return;
}
if (down > 1){Recursion(right, down-1);}
if (right > 1){Recursion(right-1, down);}
return;
}
int main() {
int i = 0, m, n;
printf("Enter value of m & n: ");
scanf("%d %d", &m, &n);
Recursion(m, n);
printf("Count: %d", count);
return 0;
}

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.