Microsoft Interview Question for Software Engineer / Developers


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]

- cobra July 23, 2012 | Flag Reply
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

- nsdxnsk July 23, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- cobra July 23, 2012 | Flag
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

- pdesai July 24, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- cobra July 24, 2012 | Flag
Comment hidden because of low score. Click to expand.
-1
of 1 vote

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

- abh007 July 24, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- cobra July 24, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@cobra can you please explain how your algorithm is working

- siva July 24, 2012 | Flag
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..

- cobra July 24, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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;

?????

- abh007 July 25, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- cobra July 25, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@cobra thank u for the explanation now i got it

- siva July 25, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- aidynamic September 23, 2012 | Flag
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];
}

- zombie July 23, 2012 | Flag Reply
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);
        }
    }

- nj August 23, 2012 | Flag Reply
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.

- loveCoding July 23, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Sounds like a DP problem.

- Anonymous July 24, 2012 | Flag Reply
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?

- Victor July 24, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- singhsourabh90 July 24, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- zero_or_one July 24, 2012 | Flag Reply
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!!!

- Dhruva Bhaswar July 24, 2012 | Flag Reply
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;

}

- anonymous July 25, 2012 | Flag Reply
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])
}

- Anonymous July 26, 2012 | Flag Reply
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

- Anonymous July 26, 2012 | Flag Reply
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];

- sukkhim July 26, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- Shakes July 27, 2012 | Flag Reply
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];

- Anonymous August 05, 2013 | Flag Reply
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.

- zero_or_one July 24, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

use djikstra algo

- jasmeet@iastate.edu September 14, 2012 | Flag Reply


Add a Comment
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.

Learn More

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.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More