Question

GoldMan Sachs | Recent Interview Experiences | Coderpad | SDE (USA) | Set-28

Answer 1

These were the questions asked for the GS coder pad (1st round)-

 

1. Compress String - aabbc - a2b2c1, a - a1
2. Find optimal path -
   Grid - [[0, 0, 0, 0, 5],
   [0, 1, 1, 1, 0],
   [2, 0, 0, 0, 0]]

 

Start is [2, 0], destination - [0, 4]
Can only go up or east(right)
Numbers denote the rocks, find the most optimal path where you go from source to destination and collect the maximum number of rocks in the process.
Output - 10

Answer 2

Code in Java(Recursive)
public class OptimalPath {
public static void main(String[] args) {
int[][] grid={{0,0,0,0,5} ,{0,1,1,1,0} ,{2,0,0,0,0}};
maxPath(grid ,2,0,0,4);
System.out.println( maxPath(grid ,2,0,0,4));
}
static int maxPath(int[][] grid , int sr, int se,int ds,int de){
System.out.println(sr+" "+se+" "+ds+" "+de);
if(ds==sr && de==se){
return grid[ds][de] ;
}
if(ds> grid.length -1|| de > grid[0].length-1 && ds < 0|| de < 0)
return 0;
int up=grid[ds][de]+maxPath(grid,sr,se,ds+1,de);
int right=grid[ds][de]+maxPath(grid,sr,se,ds,de-1);

    return Math.max(up ,right);
    //return up+right;
}
}