## Samsung Interview Question for Java Developers

Country: United States
Interview Type: Written Test

Comment hidden because of low score. Click to expand.
4
of 4 vote

The basic dynamic programming approach keeps the max so far for any given cell in a 2d array and then at each position you check whether your current max for that cell plus the value for the right cell / bottom cell is larger than the value currently in the right and bottom cell. This takes N*M space. You can reduce this to O(N+M) space by realizing that you only ever need to keep the values for the current and the next row to calculate the values for the next row.

My example below includes both versions, and the first version will print the path too.

``````package a5;

public class FindBestPath {

public static void main(String[] args) {
int [][] matrix =
{	{2,3,4,1},
{1,1,3,9},
{2,2,3,1},
{2,2,3,1}
};

//		findBestPath(matrix);
findBestPath2(matrix);
}

public static void findBestPath(int [][] matrix)
{
int [][] cost = new int[matrix.length][matrix[0].length];
int [][][] parent = new int[matrix.length][matrix[0].length][2];
for(int i = 0; i < matrix.length; i++)
{
for(int j = 0; j < matrix[0].length; j++)
{
cost[i][j] = Integer.MIN_VALUE;
parent[i][j] = new int[2];
}
}
cost[0][0] = matrix[0][0];

for(int i = 0; i < matrix.length; i++)
{
for(int j = 0; j < matrix[0].length; j++)
{
if(i+1 < matrix.length && cost[i][j] + matrix[i+1][j] > cost[i+1][j])
{
cost[i+1][j] = cost[i][j] + matrix[i+1][j] ;
parent[i+1][j][0] = i;
parent[i+1][j][1] = j;
}
if(j+1 < matrix.length && cost[i][j] + matrix[i][j+1] > cost[i][j+1])
{
cost[i][j+1] = cost[i][j] + matrix[i][j+1] ;
parent[i][j+1][0] = i;
parent[i][j+1][1] = j;
}
}
}

System.out.println("Max is " + cost[matrix.length-1][matrix[0].length-1]);
int [] at = parent[matrix.length-1][matrix[0].length-1];
System.out.print((matrix.length-1) + ":" + (matrix[0].length-1) + "(" + matrix[matrix.length-1][matrix[0].length-1] + "), ");
while(!(at[0] == 0 && at[1] == 0))
{
System.out.print(at[0] + ":" + at[1] + "(" + matrix[at[0]][at[1]] + "), ");
at = parent[at[0]][at[1]];
}
System.out.print(at[0] + ":" + at[1] + "(" + matrix[at[0]][at[1]] + "), ");
}

public static void findBestPath2(int [][] matrix)
{
int [][] cost = new int[2][matrix[0].length];
cost[0][0] = matrix[0][0];

for(int i = 0; i < matrix.length; i++)
{
int iUp = 0;
int iAt = 0;
if(i % 2 == 0)
{
iUp = 1;
iAt = 0;
}
else
{
iUp = 0;
iAt = 1;
}
for(int j = 0; j < matrix[0].length; j++)
{
if(i+1 < matrix.length && cost[iAt][j] + matrix[i+1][j] > cost[iUp][j])
{
cost[iUp][j] = cost[iAt][j] + matrix[i+1][j] ;
}
if(j+1 < matrix.length && cost[iAt][j] + matrix[i][j+1] > cost[iAt][j+1])
{
cost[iAt][j+1] = cost[iAt][j] + matrix[i][j+1] ;
}
}
}
if(matrix.length % 2 == 0)
{
System.out.println("Max is " + cost[1][matrix[0].length-1]);
}
else
{
System.out.println("Max is " + cost[0][matrix[0].length-1]);
}
}

}``````

Comment hidden because of low score. Click to expand.
0

nice one dude..

Comment hidden because of low score. Click to expand.
2
of 2 vote

O(mn) time and O(1) space.

``````#include<iostream>
using namespace std;
int minpath(int a[][5], int n)
{
for(int i=1;i<n;i++)
a[0][i] += a[0][i-1];
for(int i=1;i<n;i++)
a[i][0] += a[i-1][0];
for(int i=1;i<n;i++)
{
for(int j=1;j<n;j++)
{
a[i][j] += min(a[i-1][j],a[i][j-1]);
}
}
return a[n-1][n-1];
}
int main()
{
int a[5][5]={{1,3,7,2,1},{1,4,7,6,4},{1,2,7,1,2},{5,4,2,10,7},{3,4,5,6,7}};
cout<<minpath(a,5)<<endl;
}``````

Comment hidden because of low score. Click to expand.
0

Isnt the time complexity here is O(m+n) , how O(1) ?

also, shouldn't the sum calculation be a[i][j] += max(a[i-1][j],a[i][j-1]) ??

Comment hidden because of low score. Click to expand.
0

Isnt the time complexity here is O(m+n) , how O(1) ?

also, shouldn't the sum calculation be a[i][j] += max(a[i-1][j],a[i][j-1]) ??

Comment hidden because of low score. Click to expand.
0

If this isn't minimum path sum

Comment hidden because of low score. Click to expand.
0
of 2 vote

it will be as simple as: sum[i][j] = max(sum[i][j-1], sum[i-1][j]) + sum[i][j] but check if j-1 and i-1 doesn't go out of bounds.

i, j should start from second row and first row just add up all the left to right elements as below:

``````1 2 3 4     |   1 3 6 10
5 6 7 8     |   5 6 7 8     start from [1,0] to [m,n]``````

Second solution could be with dfs or bfs.

Comment hidden because of low score. Click to expand.
0

@aka Can you elaborate on the DFS or the BFS solution?

Comment hidden because of low score. Click to expand.
0

Just go from source node to destination node and calculate the distance for each path,basically dfs will find out all the paths and all you need to do is to keep the minimum.
Sorry but bfs won't work as each node doesn't have equal weight.

Comment hidden because of low score. Click to expand.
0

One should not disqualify the whole path based on the current adjacent cell values. The remainder of "disqualified path" may overweight the remainder of the "winning path". It's gotta be recursive

Comment hidden because of low score. Click to expand.
0
of 0 vote

public class Main {

/**
* @param args
*/
public static void main(String[] args) {

DP dp = new DP();

System.out.println(dp.f(2, 2));

}

}

class DP
{
int[][] x = {
{1, 3, 5},
{5, 4, 11},
{70, 4, 11}
};
int[][] sum = new int[10][10];

public int f(int m, int n)
{
if (sum[m][n] != 0) return sum[m][n];
int km = 0; int kn = 0;
if (m > 0) km = f(m - 1, n);
if (n > 0) kn = f(m, n - 1);
int d = Math.max(km, kn) + x[m][n];
sum[m][n] = d;
System.out.println("sum[" + m + "][" + n + "]=" + d);
return d;
}
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

The easiest way is just BFS your way through a known size matrix. You can do this by thinking of the matrix as a series of diagonals. First, its 0,0. One step away you can get 1,0 0,1. Two steps, you can get 2,0 0,2 1,1. Three steps, you get 3,0 2,1 1,2 0,3 etc, notice how it forms a diagonal across the matrix. At each step, you can calculate the max for each square on the diagonal according to the previous step. Therefore, your max space required is just X+Y or the maximum diagonal. Eventually, you'll hit the destination and you can just read off the max value. O(N*M) speed and O(N+M) storage.

Comment hidden because of low score. Click to expand.
0
of 0 vote

Samsung interview question

Comment hidden because of low score. Click to expand.
0
of 0 vote

The hidden trick in this question is the range of values. It includes INT_MAX, hence the possibility of overflow!

``````int Safe(int a, int b)
{
int sum=a+b;
if(b>0 && sum<a || b<=0 and sum>a)
return 0;
return 1;
}
i=0;j=0;sum=0;k=0;

char *Move=(char*)malloc(sizeof(char)*(m+n));
assert(Move!=NULL);
memset(Move,'-',sizeof(char)*(m+n));

while(i<n && j<m)
{
if(Safe(sum,a[i+1][j]) && Safe(sum,a[i][j+1]))
{
if(sum+a[i+1][j]>sum+a[i][j+1])
{
sum+=a[i+1][j];
i++;
Move[k++]='d';
}
else
{
sum+=a[i][j+1];
j++;
Move[k++]='r';
}
}
else if(Safe(sum,a[i+1][j]))
{
if(sum+a[i+1][j]>sum)
{
sum+=a[i+1][j];
i++;
Move[k++]='d';
}
}
else if(Safe(sum,a[i][j+1]))
{
if(sum+a[i][j+1]>sum)
{
sum+=a[[i][j+1];
j++;
Move[k++]='r';
}
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

Given the question, it seems that we have the entries of the matrix are filled with the values/weights. This can be done using DP in O(mn) and with O(1) i.e., exclusive of the space for the matrix itself.

``````sum=a[0][0];
i=0,j=0;
while(i<n && j<m)
{
if(sum+a[i+1][j]>sum+a[i][j+1])
{
sum+=a[i+1][j];
i++;
}
else
{
sum+=a[i][j+1];
j++;
}
}
return sum;``````

Comment hidden because of low score. Click to expand.
0

Greedy solution won't work here

Comment hidden because of low score. Click to expand.
0
of 0 vote

I think minimum extra space required is o(mn)

Comment hidden because of low score. Click to expand.
0
of 0 vote

Used DP... if a path is unreachable from element at (0,0) mark it as (m*n) in the dist array..
In the end we can also use this value to check that the end element is actually unreachable if the distance is >= mn

``````public static int shortestDistance(int[][] a)
{
int row = a.length;
int col = a[0].length;
int[][] dist=new int[row][col];
for(int i=0;i<row;i++)
{
for(int j=0;j<col;j++)
{
if((i==0)&&(j==0))
{
dist[i][j]=1;
}
else if(i==0)
{
if(a[i][j-1]==1)
dist[i][j]=dist[i][j-1]+1;
else
dist[i][j]=(row)*(col);
}
else if(j==0)
{
dist[i][j]=dist[i-1][j]+1;
}
else
{
if(a[i][j-1]==1)
//left element is 1, top can be either 0 or 1
dist[i][j]=Math.min(dist[i-1][j], dist[i][j-1])+1;
else
//left element is not 1
dist[i][j]=dist[i-1][j]+1;
}

}
}
return dist[row-1][col-1];

}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

Simple Code would be

public class MaximumCostPath {

static int cost[][]= {
{2,3,4,1},
{1,1,3,9},
{2,2,3,1},
{2,2,3,1}
};

static int m=cost.length,n=cost.length;

public static int getValue(int i,int j){

if(i<0||j<0){
return 0;
}
else{
return cost[i][j];
}
}

public static void getMaximumCostPath(){

for(int i=0;i<m;i++){
for(int j=0;j<n;j++){
cost[i][j]=Math.max(getValue(i,j-1)+cost[i][j], getValue(i-1,j)+cost[i][j]);
}
}
System.out.println(cost[m-1][n-1]);
}

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

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````#include <iostream>
using namespace std;

int main() {
int t;  cin>>t;

int ar[15][15];

for(int i=0;i<14;++i){
ar[i][14] = 1;
}

for(int i=0;i<14;++i){
ar[14][i] = 1;
}

ar[14][14] = 0;

for(int i=13;i>=0;--i){
for(int j=13;j>=0;--j){
ar[i][j] = ar[i+1][j] + ar[i][j+1];
}
}

while(t--){
int n,m;    cin>>n>>m;
n--;    m--;

cout<<ar[14-n][14-m]<<endl;

}
return 0;
}``````

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.