## Amazon Interview Question

Software Engineer / Developers**Team:**SDE

**Country:**India

**Interview Type:**In-Person

I think the answer for first question is (p+q)c(p). Lets say the path from top left to bottom right involves of Right ('R') and down ('D') moves. so, the ultimate path would look like a string with characters 'R' and 'D'. we know that we need to have q number of 'R's and p number of 'D's to build this string. so, in how many ways can we place "p" amount of 'D's and "q" amount of 'R's to build a string. Answer is (p+q)c(p).

For second part, it is kind of vague. It does look like we can loop forever without reaching bottom right.

Ans1: (P+Q) choose P times.

Ans2: P power Q times ( for all 4 possible way).

Ans3: Use Combinatorics and Inclusion exlucsion principle.

suppose the points (m,n) are blocked where m<P and n <Q.

then

(P+Q) choose p - (all the points from origin to M,n) ( all the points from m,n to P and Q).

In order to reach the bottom, we gotta move RIGHT (q - 1) times and DOWN (p -1) times, so talking permutation, the number of unique combinations of result string would be ((p -1)! * (q - 1))! / (p - 1)! * (q - 1)! to compensate for the duplicates.

This is the logic behind this answer:

If there are n items and r of them are alike(nondistiguishable), the different no. of arrangements of these n items will be n! / r! where n!=1.2.3...n

For example if there are four letters A,B,C,D then different no. of arrangements will be

4!=1.2.3.4=24. But if two of them are alike, ie if the letters are A,A,B,C then the different no. of arrangements will be reduced to 4! / 2! because now no need to consider the internal arrangements of two A's.

In our case, we need a result that has q R's and p D's. Hence the answer.

And the code would be -

- Dragon March 04, 2012