Question

GoldMan Sachs | Recent Interview Experiences | Coderpad | SDE | Set-23

Answer 1

Today I had my coderpad round with GS. We dived straight into the code. This was the First question: https://leetcode.com/discuss/interview-question/1837422/Goldman-Sachs-or-Coderpad-or-First-non-repeating-character

Second question:

Variant of: https://leetcode.com/problems/minimum-path-sum/

A 2D array 'arr' was given with m rows and n columns. arr[i][j] represents the amount of gold present in the cell. I needed to find the maximum gold that can be collected while going from the bottom-left cell (arr[m-1][0]) to the top-right cell (arr[0][n-1]).

We can only travel in the top and the right direction.

Input:
[[0,0,0,0,5]]
[[0,1,1,1,0]]
[[2,0,0,0,0]]

Output:
10

Used a dp array and travelled from the destination to the source while maintaining the maximum of the two cells from the top and the right direction.

Third question:
https://leetcode.com/discuss/interview-question/1837497/Goldman-Sachs-or-Coderpad-or-Find-the-largest-tree

Hope it helps!

Answer 2

second question:
public class MaxGold {

public static int findMaxGold(int[][] grid) {

    int m = grid.length;
    int n = grid[0].length;

    int[][] dp = new int[m][n];

    for (int i = m - 1; i >= 0; i-- ) {
        for (int j = 0; j < n; j++ ) {
            dp[i][j] += grid[i][j];

            if ( i < m - 1 && j > 0) {
                dp[i][j] += Math.max(dp[i + 1][j], dp[i][j - 1]);
            }
            else if (i < m - 1) {
                dp[i][j] += dp[i + 1][j];
            }
            else if ( j > 0) {
                dp[i][j] += dp[i][j - 1];
            }
        }
    }

    return dp[0][ n -1];

}
public static void main(String[] args) {

    //start from bottom left and destination top right, can move only up and right.
    int[][] grid = {{0,0,0,0,5},
                    {0,1,1,1,0},
                    {2,0,0,0,0}};

    System.out.println(findMaxGold(grid));
}
}