CareerCup

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

}

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

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.

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

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.

Samsung interview question

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

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;

I think minimum extra space required is o(mn)

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

	}

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

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