5 weeks ago

John 910

Hyderabad

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:

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

3 months ago

Ujjwal Srivastava 320

Bengaluru

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

7 months ago

Nitai Das • 20

Bengaluru

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;
    }
};