Question: Amazon Intership Interview Experience, NIT Raipur, August 2022
1
Entering edit mode

# Amazon Internship Interview Experience

Campus: NIT Raipur

Initial Shortlisting: Based in CGPA

After clearing first round of shortlisting, got call for Interview.

Interview (1 Round)

Round 1 : (Technical Round)

There was only one interview round which went for an hour. It took place on Amazon Chime platform.

Interview started off with a short introduction. After my brief introduction, interviewer stated the first problem which was

Question 1

Given a grid of size m * n, let us assume you are starting at (0, 0) and your goal is to reach (m-1, n-1). At any instance, if you are on (x, y), you can either go to (x, y + 1) or (x + 1, y).

Now consider if some obstacles are added to the grids. How many unique paths would there be?

An obstacle and empty space are marked as 1 and 0 respectively in the grid.

Input:

`````` [[0, 0, 0],
[0, 1, 0],
[0, 0, 0]]
``````

Output:

``````2
``````

A standard dynamic programming problem. Firstly, explain why greedy will fail here, then give a recursive solution for the problem then memoize the recursive code and then give a tabulation solution along with there time and space complexities. (To make an impact on the interviewer you can also provide a space optimized approach.)

Then he moved on to the second problem

Question 2

Given a Binary Tree print all leaf nodes in recursive fashion maintaining the order in which they appear

Note: you have to solve it only using recursion you cannot use any other method.

Input:

``````          1
/    \
2        3
/  \       /
4    5     6
\
7
``````

Output:

``````[, [4,5,6], [2,3], ]
``````

Explanation: You need to print all the leaf nodes than delete it the nodes which now becomes a leaf node will be printed next until the root becomes NULL.

I struggled a bit in this problem and asked for a hint which was to think of heights. (It makes a good impact if you come up with a solution after struggling using a small hint). I came up with an approach of using heights of each node as index and store them in my answer vector. 7 is at 0th height store it in 0th index. 6 is at height one store it in first index and recursive compute the answer for rest.

He was satisfied with my approach and ended the interview asking for any questions.

• Tech stacks used in Amazon

Verdict: Selected

0
Entering edit mode

## Question1

Overview

• You are given an m x n integer array grid. The top-left corner is (i.e., grid). The bottom-right corner is (i.e., grid[m - 1][n - 1]).
• You can only move either down or right at any point in time.
• Now some obstacle gets added to the grid.
• An obstacle is marked by 1 and free space by 0.
• A path cannot include any square that is an obstacle.
• Return the number of possible unique paths that the robot can take to reach the bottom-right corner.

Solution

• This problem can be solved using dynamic programming.
• The dimensions of the dp will be m x n i.e dp[m][n].
• Now initialize the dp with 0.
• Now if the current cell is an obstacle then dp[i][j]=0, where i the current row and j is the current column.
• If the current cell is not an obstacle then the transition would be dp[i][j] = dp[i-1][j]+ dp[i][j-1], where dp[i-1][j] is the number of ways in which we can reach cell above the current cell from where we can come to the current cell and dp[i][j-1] is the number of ways in which we can reach cell left side of the current cell from where we can come to the current cell.
• Thus in this way at last the final answer would be dp[m-1][n-1].

Code

``````ll n = obstacleGrid.size();
ll m = obstacleGrid.size();
ll dp[n][m];
mem0(dp);
for (ll i = 0; i &lt; n; i++)
{
for (ll j = 0; j &lt; m; j++)
{
if (i == 0)
{
if (!obstacleGrid[i][j])
{
if (j == 0)
dp[i][j] = 1;
else
dp[i][j] += dp[i][j - 1];
}
else
{
dp[i][j] = 0;
}
}
else if (j == 0)
{
if (!obstacleGrid[i][j])
{
dp[i][j] += dp[i - 1][j];
}
else
{
dp[i][j] = 0;
}
}
else
{
if (!obstacleGrid[i][j])
{
dp[i][j] += (dp[i - 1][j] + dp[i][j - 1]);
}
else
{
dp[i][j] = 0;
}
}
dp[i][j] %= mod;
}
}
return dp[n - 1][m - 1];
``````