## Microsoft Interview Question Software Engineer / Developers

- 0of 0 votes
A table composed of N*M cells,each having a certain quantity of apples, is given. you start from the upper-left corner. At each step you can go down or right one cell.Design an algorithm to find the maximum number of apples you can collect ,if you are moving from upper-left corner to bottom-right corner.

**Country:**India

**Interview Type:**In-Person

I don't believe it's sufficient enough. Consider following case. Also, you need to consider the border conditions e.g.) when x=m, only down, when y=n only right

1,2,3,4

1,1,1,1

9,9,9,9

i don't understand what you are saying.. for your case answer is 38 (path: 1 1 9 9 9 9) and is achieved by the code i submitted..

small changes.. replace M to M-1 and N to N-1 in the snippet i gave..

check the solution here: ideone.com/Gtpyn

@siva: this algorithm is just simple

1. you have to traverse each cell in 2D array

2. you have to compute maximum number of apples in each cell of 2D array...

after the computation of 2D array.. just print all the values in array form.. you will be clear..

ya got it finally.....thanx..@cobra..

But i think there is a mistake..in 2nd line of code, there should be

array[0....M] [0]=0;

?????

/// Using Dynamic Programming

/// t[ix][iy] = map[ix-1][iy-1] + max(t[ix-1][iy], t[ix-1][iy])

inline int max(int a, int b)

{

return (a < b) ? b : a;

}

int apple_collect()

{

int map[4][4] = {

{10, 9, 1, 2},

{3, 4, 3, 4},

{1, 2, 5, 8},

{8, 2, 3, 5}

};

int t[5][5];

memset(t, 0, sizeof(t));

int ix = 0, iy = 0;

for(ix = 1; ix <= 4; ix ++)

{

for(iy = 1; iy <= 4; iy ++)

{

int mx = max(t[ix-1][iy], t[ix][iy-1]);

mx += map[ix-1][iy-1];

t[ix][iy] = mx;

}

}

return t[4][4];

}

ITERATIVE:

```
public static int[][] getMaximalCostMatrix(int[][] valueMatrix)
{
int[][] costMatrix= new int[valueMatrix.length][valueMatrix[0].length];
costMatrix[0][0]= valueMatrix[0][0];
for(int i=1; i<costMatrix.length; i++)
{
costMatrix[i][0]= valueMatrix[i][0] + costMatrix[i-1][0];
costMatrix[0][i]= valueMatrix[0][i] + costMatrix[0][i-1];
}
for(int i=1; i<costMatrix.length; i++)
{
costMatrix[i][i]= valueMatrix[i][i] + max(costMatrix[i-1][i], costMatrix[i][i-1]);
for(int j=i+1; j<costMatrix.length; j++)
{
costMatrix[i][j]= valueMatrix[i][j] + max(costMatrix[i-1][j], costMatrix[i][j-1]);
costMatrix[j][i]= valueMatrix[j][i]+ max(costMatrix[j-1][i], costMatrix[j][i-1]);
}
}
return costMatrix;
}
```

RECURSIVE

```
public static void getMaximalCostMatrix(int[][] valueMatrix, int[][] costMatrix, int i, int j)
{
if(i==0&&j==0)
costMatrix[i][j]= valueMatrix[i][j];
else
{
if(i-1>=0&&costMatrix[i-1][j]==0)
getMaximalCostMatrix(valueMatrix, costMatrix, i-1, j);
if(j-1>=0&&costMatrix[i][j-1]==0)
getMaximalCostMatrix(valueMatrix, costMatrix, i, j-1);
int p= i-1>=0?costMatrix[i-1][j]:0;
int q= j-1>=0?costMatrix[i][j-1]:0;
costMatrix[i][j]= valueMatrix[i][j] + max(p,q);
}
}
```

I don't get the question in the first place. Don't you think that parsing the whole 2D array will give the maximum? Or I might be missing something?

```
#include<stdio.h>
#define max(a,b) ((a)>(b) ? (a) : (b))
int main(){
int a[1001][1001],m,n,i,j;
scanf("%d%d",&n,&m);
for(i=0;i<n;i++)
for(j=0;j<m;j++)
scanf("%d",&a[i][j]);
for(i=n-2;i>=0;i--)
a[i][m-1]+=a[i+1][m-1];
for(j=m-2;j>=0;j--)
a[n-1][j]+=a[n-1][j+1];
for(i=n-2;i>=0;i--)
for(j=m-2;j>=0;j--)
a[i][j]+=max(a[i+1][j],a[i][j+1]);
printf("%d\n",a[0][0]);
return 0;
```

}

How about this soln, simple recursion algo.

Function Signature Find(A, M, N, i, j, S)

A[M][N] - 2-D array

i,j - Starting coordinates(1,1) (I am assuming indexing from 1)

S - initially 0

Find(A, M, N, i, j, S)

{

if(i==M && j==N)

return S + A[i][j];

else

{

int S1=0, S2=0;

if(i<M)

{

S1 = Find(A, M, N, i+1, j, S + A[i][j]);

}

if(j<N)

{

S2 = Find(A, M, N, i, j+1, S + A[i][j]);

}

return S1>=S2 ? S1 : S2 ;

}

}

```
int n, m;
vector< vector<int> > dp(n, vector<int>(m, 0));
dp[0][0] = a[0][0];
for (int j=1; j < m; j++)
dp[0][j] += dp[0][j-1];
for (int i=1; i < n; i++)
dp[i][0] += dp[i-1][0];
for (int i=1; i < n; i++) for (int j=1; j < m; j++)
dp[i][j] = a[i][j] + max(dp[i][j-1], dp[i-1][j]);
return dp[n-1][m-1];
```

use

```
for all i from 0 to M
for all j from 0 to N
if i and j both 0 continue;
else if only i is 0 apples[i][j] += apples[i][j-1]
else if only j is 0 apples[i][j] += apples[i-1][j]
else apples[i][j] += max( apples[i-1][j] + apples[i][j-1] )
```

the cell at extreme bottom-right will give the maximum apples that can be collected.

the maximum sum is stored in array[M][N]

- cobra on July 23, 2012 Edit | Flag Reply