Amazon Interview Question for SDE-2s

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

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

1. It is a typic combination problem.
For (0,0) to (i, j) is C(i+j, i) = (i+j)!/i!/j!
2. If there are blocks on the way, then, dynamic programming is needed for performance.
It is just a reverse way to calculate f(i, j) = f(i - 1, j) + f(i, j-1) with special cases some f(x, y) = 0.

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

Hey, these are standard DP problems. Identify each subproblem as the number of ways you can reach the location (k,l) starting from (0,0), then it can be calculated as the sum of the number of ways reaching (k-1,l) and (k,l-1), and you can use either bottom-up approach or a top-down memorization approach to solve it. When there are blocks, you just need to put additional checks inside the code before you sum them. These questions are given in LeetCode Online Judge that not only allows you to type in your (Java or C++) code in a panel, but also checks if it is correct and if its performance is not exponential.

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

@vqeek what u have given is a way....in question they ask for how many ways are possible...we can go right down right down....zigzag path..

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

Please let me know if the following dynamic programming approach is correct:

``````t[0][0]=0; //target location i.e., bottom-right corner
for(i=n-2;i>=0;i--)
t[n-1][i]=1;//there is only one way for the last row blocks since moving up is prohibited and moving down will lead us off the grid
for(i=n-2;i>=0;i--)
t[i][n-2]=1; //there is only one way for the last column blocks since moving right leads us off the grid and we are not allowed to go to the left
j=n-3;i=n-3;
while(i>=0 && j>=0)
{
if(t[i+1][j]>=t[i][j+1]) //we are looking for the maximum number of ways hence >=
t[i][j]=t[i+1][j]+1;
else
t[i][j]=t[i][j+1]+1;
}
return t[0][0];``````

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

Sorry, my mistake! the first line is actually t[n-1][n-1]=0 i.e., the bottom-right corner :)

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

``````class Program
{
static void Main(string[] args)
{
GridPath p = new GridPath(1,1);
p = new GridPath(2, 2);
p = new GridPath(3, 3);
p = new GridPath(4, 4);
p = new GridPath(5, 5);
p = new GridPath(6, 6);
p = new GridPath(7, 7);
p = new GridPath(8, 8);
p = new GridPath(9, 9);
}

public class GridPath
{
static int possibilitiesFound;
static int N;  //width
static int M;  //height
public GridPath(int width, int height)
{
possibilitiesFound = 0;
N = width;
M = height;
StepPath(1, 1);
Console.WriteLine(possibilitiesFound);
}
private static void StepPath(int i, int j)
{
// check for blocks and return if found, for instance: if ((i == 2) && (j == 2)) return;

if (j < M) { StepPath(i, j + 1); }
if(i < N) { StepPath(i + 1, j); }
if ((j == M) && (i == N)) { possibilitiesFound++; }
}
}
}``````

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

``````int getways(int N, int M, int r, int c) { // target is cell[r,c]
int[] store = new int[N];
if(c==0)
return 1;
store[0] = 1;

for(int i=0; i<N; i++)
for(int j=1; j<M; j++) {
store[j] += store[j-1];
if(i==r && j==c)
return store[j];
}
}``````

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

Standard Backtracking Problem

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

Cant we solve this problem straightaway. I mean if you start with (0,0) and if you have to move to any arbitrary location (i,j) while moving either to the right or bottom in one step then.
Consider the location (3,5) then to reach (3,5) from (0,0) the number of steps are 8 that is 3+5 as you either increase the row number by one or column number by one. So to reach the location (i,j) the number of steps involved are (i+j).Here the shortest path does not matter as you cannot move diagonally .You can only move either right or down. Correct me if i am wrong

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

``````static int getWays(int toX, int toY)
{
if (toX == 0 || toY == 0)
return 1;
else
return getWays(toX - 1, toY) + getWays(toX, toY - 1);
}``````

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

This a right solution using Recursive approach.
But, how do we acheive it using iterative method. Can anyone provide the iterative approach please?

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.