Entering edit mode

**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**

Click here to Practice

Submit Problem to OJ

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:**

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

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

Few questions I asked:

- About team switches
- Tech stacks used in Amazon

**Verdict: Selected**

Entering edit mode

**Overview**

- You are given an m x n integer array grid. The top-left corner is (i.e., grid[0][0]). 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[0].size();
ll dp[n][m];
mem0(dp);
for (ll i = 0; i < n; i++)
{
for (ll j = 0; j < 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];
```

Loading Similar Posts