Amazon Interview Question
Software Engineer / DevelopersTeam: 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