Amazon Interview Question for Software Engineer / Developers

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

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

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 -

``````void reachBottom(str Matrix[], int level, int i, j, int p, int q)
{
if ( i == p && j == q)
cout<<matrix;
if ( i < p )
{
str[level++] = 'D';
reachBottom(str, level, i+1, j, p, q);
}
if ( j < q )
{
str[level++] = 'R';
reachBottom(str, level, i, j + 1, p, q);
}
}``````

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

Mathematics is wrong. But correct code!

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

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.

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

u r correct..

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

CTCI book has a good explanation... if possible have a look at that

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

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).

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

T(1xq) = 1
T(px1) = 1
T(pxq) = T(px(q-1)) + T((p-1)xq)

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.
{"found_math": false, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 0, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0, "katex": 0, "math-container": 0, "wp-katex-eq": 0, "align": 0, "equation": 0, "x-ck12": 0, "texerror": 0}