Microsoft Interview Question 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 on 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 on 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 on 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 on 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 on July 24, 2012 | Flag
Comment hidden because of low score. Click to expand.
-1
of 1 vote

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

- abh007 on 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 on 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 on July 24, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@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 on 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 on 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 on 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 on 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 on 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 on 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 on 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 on July 23, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Sounds like a DP problem.

- Anonymous on 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 on 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 on 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 on 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 on 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 on 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 on 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 on 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 on 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 on 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 on 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 on July 24, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

use djikstra algo

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


Add a Comment
Name:

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

Books

is a comprehensive book walking you through 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