Question: Amazon Intership Interview Experience, NIT Raipur, August 2022

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

Click here to Practice

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:

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

ADD COMMENT • link

Entering edit mode

Question1

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 &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];

ADD COMMENT • link 2.0 years ago Ujjwal Srivastava 320

Entering edit mode

QUESTION 2 :Reverse print of leave Nodes

class Solution {
public:
map<int, vector<int>> mp;

void call(Node* root, int l) {
if (root == NULL) {
return;
}
mp[l].push_back(root->data);
call(root->left, l + 1);
call(root->right, l + 1);
}

int findMaxForN(Node* root, int n) {
call(root, 0);

for (auto it=mp.rbegin() ; it!=mp.rend() ; it++) {

for (int val : it->second) {
cout << val << " ";
}
cout << endl;
}
return -1;
}
};

ADD COMMENT • link 8 months ago Nitai Das • 20