Microsoft Interview Question for Software Engineer / Developers

• 0

Country: India
Interview Type: In-Person

Comment hidden because of low score. Click to expand.
6
of 8 vote

``````array[0][0...N] = 0;
array[0...M][0]=0;
for i=1 to M
for j=1 to N
if(array[i-1][j] >= array[i][j-1])
array[i][j] += array[i-1][j]
else
array[i][j] += array[i][j-1]``````

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

Comment hidden because of low score. Click to expand.
-1
of 1 vote

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

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

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..

Comment hidden because of low score. Click to expand.
-1
of 1 vote

No .. in that case .. considering the algorithm, the answer is 1 2 3 4 1 9

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

small changes.. replace M to M-1 and N to N-1 in the snippet i gave..
check the solution here: ideone.com/Gtpyn

Comment hidden because of low score. Click to expand.
-1
of 1 vote

still the same.....not getting 38..

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

it is 38 only.. check the solution in the link ideone.com/Gtpyn

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

Comment hidden because of low score. Click to expand.
-1
of 1 vote

@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..

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

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;

?????

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

@abh007: Sorry for that mistake.. you are right.. now the content is edited

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

@cobra thank u for the explanation now i got it

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

Should'nt the answer be 206m with path (1, 100, 100, 2, 3) for following..

{{
{1, 2, 3, 6},
{100, 2, 6, 10},
{100, 2, 3, 3}
}}

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

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

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

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

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

It can be done using Dynamic Programming, We will start with bottom right point and build it up.

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

Sounds like a DP problem.

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

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?

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

you are missing the fact that :-
if only down and right move's are allowed then you can cover atmost . 2*N-1 box for NXN matrix.

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

Correction : the last line should not contain a + inside max()

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

this can be solved using modified dijkstra algorithm , just u gonna use max-priority queue in place of min and some more minor modifications... atleast that is wat i think!!!

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

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

}

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

let the ip array be a[m][n]
op=max sum int
---------------
i=j=0;
sum=0;
int fuc(i,j)
{
sum+=a[i][j]
if(i==m-1 && j==n-1)
return sum;
else
return max (fuc(a[i][j+1]) ,fuc(a[i+1][j])
}

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

please comment on the above code and let me kno if i'm right
-krPESIT

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

for(int i=1;i<4;i++)
for(int j=1;j<5;j++)
if(array[i-1][j]>=array[i][j-1])
array[i][j]+=array[i-1][j];
else
array[i][j]+=array[i][j-1];

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

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

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

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

Comment hidden because of low score. Click to expand.
-1
of 1 vote

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.

Comment hidden because of low score. Click to expand.
-1
of 1 vote

use djikstra algo

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.