## Microsoft Interview Question for Software Engineer / Developers

Country: India
Interview Type: Phone Interview

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

Using DP:
opt[i][j]=max{opt[i+1][j], opt[i+1][j+1]}

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

Solution using DP in Python. O(n^2).

``````def enumerate_reversed(L):
for index in reversed(xrange(len(L))):
yield index, L[index]

def get_path_with_max_weight(input_list):
"""
Given n rows with integers, returns the Path instance having the maximum weight.
"""
n_rows = len(input_list)

# This solution uses Dynamic programming:
# opt[i][j] = input[i][j] + max(opt[i+1][j]), opt[i+1][j+1])
# A nxn matrix is used to store the optimal weight values for each substructure.
# Each element (i,j) of the matrix is a tuple of -
# (optimal weight at (i,j), column of element selected at the i+1 row)
opt_mat = [[(0, -1) for col in range(n_rows)] for row in range(n_rows - 1)]
opt_mat.append([(val, -1) for val in input_list[n_rows - 1]])

for i, in_row in enumerate_reversed(input_list):
opt_row = opt_mat[i]
if i < (n_rows - 1):
for j, val in enumerate(in_row):
k = j if opt_mat[i+1][j] > opt_mat[i+1][j+1] else j+1
opt_row[j] = (val + opt_mat[i+1][k][0], k)

# Construct the path sequence
max_weight, next_elem_col = opt_mat[0][0]
max_weight_path = []
row = 0
max_weight_path.append(input_list[row][0])
while (next_elem_col != -1):
row += 1
max_weight_path.append(input_list[row][next_elem_col])
next_elem_col = opt_mat[row][next_elem_col][1]

return max_weight, max_weight_path

def getInput():
n = int(raw_input("How many rows? "))
input_list = list()
for i in range(n):
prompt_str = "[Row %d] Enter %d numbers: " % (i+1, i+1)
str_row_input = raw_input(prompt_str)
input_list.append(map(int, str_row_input.split()))
return input_list

ilist = getInput()
#ilist = [[4], [2, 9], [15, 1, 3], [16, 92, 41, 44], [8, 142, 6, 4, 8]]
print "Path with maximum weight (%d) is %r" % get_path_with_max_weight(ilist)``````

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

Correct formula should be:
OPT[i][j] = Arr[i][j] + max (OPT[i-1][j-1], OPT[i-1][j])

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

If we can solve this with the combination of maximum subarray problem and backtracking, I don't see any use for DP since there is no recalculation of any kind.

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

``````/**
* The naive solution is to enumerate all possible paths and pick the maximum.
* Complexity analysis of this solution is somewhat complicated,
* but with a little work one can see that their are nC1 + nC2 + ... nCn possible paths, where nCm means "n choose m".
* Think Pascal's Triangle.
*
* However there is a better way.
* This can be transformed into the longest path problem for a directed acyclic graph.
* The longest path problem has known solution with time complexity equal to the number of vertices. See wikipedia.
*
* 1) Consider graph A to be the input and graph B to be an auxiliary graph with the same structure as graph A.
*    Graph B will store the maximum path weight possible for a path ending on that node.
* 2) Perform a breadth first traversal of A and store the sum of each node's weight and the maximum weight of its parents in graph B.
* 3) Starting at the bottom node of graph B with the maximum value, traverse B by navigating to the parent with maximum value.
*    This path is the path with the maximum weight.
*
* Time O(n^2), Space O(n^2)
*/
int maxWeight(int a[][]) {

// Build graph B.
int max = 0;
int maxJ = 0;
int b[][] = new int[a.length][a.length];
for (int i = 0; i < a.length; ++i) {
for (int j = 0; j <= i; ++j) {
b[i][j] = a[i][j];
int up = 0;
int diagonal = 0;
if (i > 0) {
up = b[i-1][j];
if (j > 0) {
diagonal = b[i-1][j-1];
}
}
b[i][j] += Math.max(up, diagonal);
if (b[i][j] > max) {
max = b[i][j];
maxJ = j;
}
}
}

// Follow max path in B from bottom to top.
int weight = a[0][0];
int j = maxJ;
for (int i = a.length - 1; i > 0; --i) {
weight += a[i][j];
int up = b[i-1][j];
int diagonal = 0;
if (j > 0) {
diagonal = b[i-1][j-1];
}
if (diagonal > up) {
j--;
}
}

return weight;
}``````

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

Here is my solution using backtracking. First we will find the sum of max scaled path and then we will find the actual path.

``````#include <iostream>
using namespace std;

int MaxPath(int** mat,int n,int row,int col)
{
if (row >= n ||col >= n) return 0;
return mat[row][col] + max<int>(
MaxPath(mat,n,row+1,col),
MaxPath(mat,n,row+1,col + 1) );

}

bool PrintmaxPath(int** mat,int n,int row,int col,int pathLength)
{

if(row  >= n || col  >= n )
if(pathLength == 0)return true;
else return false;

if(PrintmaxPath(mat,n,row+1,col,pathLength - mat[row][col]))
{
cout<<mat[row][col]<<'\t';
return true;
}
if(PrintmaxPath(mat,n,row+1,col + 1,pathLength - mat[row][col]))
{
cout<<mat[row][col]<<'\t';
return true;
}

}

int main(int argc, char** argv) {
int n;
cin >> n;
int ** mat = new int* [n];
for(int i = 0; i < n; i++)
mat[i] = new int [n];

for(int i = 0; i < n ; i++)
for(int j = 0; j <= i; j++)
cin >> mat[i][j];

int maxL = MaxPath(mat,n,0,0);
PrintmaxPath(mat,n,0,0,maxL);
cout << " Max weight is: "<<maxL<<endl;

return 0;
}``````

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

This algorithm's complexity is O(2^N). better to use DP.

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

Modification for anonymous's post:
DP approach:

``OPT[x][y] = weight of the optimal path from cell (1,1) to cell (x,y).``

The correct recursive formula should be:

``````OPT[i][j] = Arr[i][j] + max (OPT[i-1][j], OPT[i-1][j-1]);
Since we can go to cell (i,j) from either cell (i-1,j) downward; or from (i-1,j-1) diagonally downward to the right.``````

Initial values:

``````OPT[i][j] = 0; for all i, j;
OPT[1][1] = Arr[1][1]; // indices start from 1``````

``ANS = max(OPT[n][i]) for i = 1..n;``

Can be implemented in O(n^2) time and space;

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

``````int res = 0;
public void maxweight(int[][] table) {

go(table, 0, 0, 0);

System.out.println("res:" + res);

}

public void go(int[][] table, int i, int j, int sum) {

if(i == table.length-1 ) {
res = Math.max(res, sum + table[i][j]);
return;
}

go(table, i+1, j, sum + table[i][j]);
go(table, i+1, j+1, sum + table[i][j]);

}``````

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

``````#define DIMM 5

int sampleArray[DIMM][DIMM] =
{
{4,  0,   0, 0, 0},
{2,  9,   0, 0, 0},
{15, 1,   3, 0, 0},
{16, 92, 41, 44,0},
{8, 142,  6, 4, 8},
};

int GetMaxWeight(int row, int col, int (&path)[DIMM], const int (&arr)[DIMM][DIMM])
{
if(row >= 0 && row < DIMM && col >= 0 && col < DIMM)
{
path[row] = arr[row][col];

int testPathDown[DIMM];
memcpy(&testPathDown, &path, sizeof(int) * DIMM);

int testPathDiag[DIMM];
memcpy(&testPathDiag, &path, sizeof(int) * DIMM);

int down = GetMaxWeight(row+1, col, testPathDown, arr);
int diag = GetMaxWeight(row+1, col+1, testPathDiag, arr);
if(down > diag)
{
memcpy(&path, &testPathDown, sizeof(int) * DIMM);
return down;
}
else
{
memcpy(&path, &testPathDiag, sizeof(int) * DIMM);
return diag;
}
}
else
{
// just sum up the path and get out
int sum = 0;
for(int i = 0; i < DIMM; i++)
{
sum += path[i];
}

return sum;
}
}

int main()
{
int path[DIMM] = {0,0,0,0,0};

printf("Max Weight is: %d", GetMaxWeight(0, 0, path, sampleArray));

return 0;
}``````

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

``````public class MaxWeightPathTraversal {

static int[][] input =  {{4}, {2,9}, {15, 1, 3 }, {16, 92, 41, 44 }, {8, 142, 6, 4, 8 }};
static Triple<Integer, Integer, Integer>[][] dpTable = new Triple[input.length][input.length];

public static void main(String...args){
populateDPTable();
printMaxPath();
}

private static void printMaxPath() {
Triple<Integer, Integer, Integer> maxValue = Triple.of(Integer.MIN_VALUE, -1, -1);
StringBuilder str = new StringBuilder();
for(int i=0; i<dpTable[dpTable.length-1].length; i++){
Triple<Integer, Integer, Integer> t = dpTable[dpTable.length-1][i];
if(t != null){
if(maxValue.getLeft() < t.getLeft()){
str = new StringBuilder();
maxValue = t;
str.insert(0, input[dpTable.length-1][i] + ",");
}
}
}

while(true){
int x = maxValue.getMiddle();
int y = maxValue.getRight();
if(x == -1 && y == -1){
break;
}
str.insert(0, input[maxValue.getMiddle()][maxValue.getRight()] + ",");
maxValue = dpTable[maxValue.getMiddle()][maxValue.getRight()];
}
System.out.println(str);
}

private static void populateDPTable(){
dpTable[0][0] = Triple.of(input[0][0], -1, -1);
for(int i=0; i<input.length-1; i++){
for(int j=0; j<input[i].length; j++ ){
if(dpTable[i+1][j] == null){
dpTable[i+1][j] = Triple.of(dpTable[i][j].getLeft()+input[i+1][j], i,j);
}else if(dpTable[i][j].getLeft()+input[i+1][j] > dpTable[i+1][j].getLeft()){
dpTable[i+1][j] = Triple.of(dpTable[i][j].getLeft()+input[i+1][j], i,j);
}

if(dpTable[i+1][j+1] == null){
dpTable[i+1][j+1] = Triple.of(dpTable[i][j].getLeft()+input[i+1][j+1], i,j);
}else if(dpTable[i][j].getLeft()+input[i+1][j+1] > dpTable[i+1][j+1].getLeft()){
dpTable[i+1][j+1] = Triple.of(dpTable[i][j].getLeft()+input[i+1][j+1], i,j);
}

}
}
}

}``````

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

``````# your code goes here
a=[]
n=int(raw_input())
for i in xrange(n):
a.append(map(int, raw_input().split(' ')))

l=[[(0,-1) for x in xrange(len(a))] for x in xrange(len(a)-1)]

l.append([(x,-1) for x in a[len(a)-1] ])

for i in reversed(xrange(len(l)-1)):
for j in reversed(xrange(len(a[i]))):
l[i][j]=(a[i][j]+max(l[i+1][j][0],l[i+1][j+1][0]) ,(j if l[i+1][j][0]>l[i+1][j+1][0] else j+1))
print l
i=0
j=0
while  i<len(a):
print a[i][j]," ",;
j=l[i][j][1]
i+=1``````

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

simple solution :

``````#include <iostream>
#include <cmath>
using namespace std;
int findMaxPath(int mat[][100],int n,int i,int j,int k)
{

if(i>=n||j>=k)return 0;
return mat[i][j]+max(findMaxPath(mat,n,i+1,j,k+1),findMaxPath(mat,n,i+1,j+1,k+1));
}
int main() {
int n,mat[100][100],i,j;
cin>>n;
for(i=0;i<n;i++)
{
for(j=0;j<=i;j++)
cin>>mat[i][j];
}
cout<<findMaxPath(mat,n,0,0,1)<<endl;
return 0;
}``````

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

This code uses recursive approach to solve it

``````class MaxPathTriangleMetrix
{

int[][] Matrix = new int [5][];

public MaxPathTriangleMetrix()
{
InitializeMatrix();
}

public void PrintMaxPath()
{
List<string> path = new List<string>();
path.Add("Start at " + Matrix[0][0]);
Console.WriteLine("Max path weight is :" + GetPathWeight(0, 0, path));
string msg = string.Empty;
foreach(string move in path)
{
Console.WriteLine(move);
}
}
private int GetPathWeight(int row, int col, List<string> path)
{
if ((row + 1) == Matrix.GetLength(0))
{
return Matrix[row][col];
};
List<string> path1List = new List<string>();
List<string> path2List = new List<string>();
int path1 = GetPathWeight(row + 1, col, path1List);
int path2 = GetPathWeight(row + 1, col + 1, path2List);
if (path1 > path2)
{
path.Add("Move to " + Matrix[row + 1][col]);
return path1 + Matrix[row][col];
} else
{
path.Add("Move to " +Matrix[row + 1][col + 1]);
return path2 + Matrix[row][col];
}

}

public void PrintMatrix()
{
for(int row = 0; row < 5; row++)
{
for (int column = 0; column <= row; column++)
{
Console.Write(Matrix[row][column] + ", ");
}
Console.WriteLine();
}
}

private void InitializeMatrix()
{
var rand = new Random(DateTime.Now.Millisecond);
for(int row = 0; row < 5; row++)
{
Matrix[row] = new int[row + 1];
for (int column = 0; column <= row; column++)
{
Matrix[row][column] = rand.Next(1, 10);
}
}
}
}``````

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

It can be solved using recursive approach

``````class MaxPathTriangleMetrix
{

int[][] Matrix = new int [5][];

public MaxPathTriangleMetrix()
{
InitializeMatrix();
}

public void PrintMaxPath()
{
List<string> path = new List<string>();
path.Add("Start at " + Matrix[0][0]);
Console.WriteLine("Max path weight is :" + GetPathWeight(0, 0, path));
string msg = string.Empty;
foreach(string move in path)
{
Console.WriteLine(move);
}
}
private int GetPathWeight(int row, int col, List<string> path)
{
if ((row + 1) == Matrix.GetLength(0))
{
return Matrix[row][col];
};
List<string> path1List = new List<string>();
List<string> path2List = new List<string>();
int path1 = GetPathWeight(row + 1, col, path1List);
int path2 = GetPathWeight(row + 1, col + 1, path2List);
if (path1 > path2)
{
path.Add("Move to " + Matrix[row + 1][col]);
return path1 + Matrix[row][col];
} else
{
path.Add("Move to " +Matrix[row + 1][col + 1]);
return path2 + Matrix[row][col];
}

}

public void PrintMatrix()
{
for(int row = 0; row < 5; row++)
{
for (int column = 0; column <= row; column++)
{
Console.Write(Matrix[row][column] + ", ");
}
Console.WriteLine();
}
}

private void InitializeMatrix()
{
var rand = new Random(DateTime.Now.Millisecond);
for(int row = 0; row < 5; row++)
{
Matrix[row] = new int[row + 1];
for (int column = 0; column <= row; column++)
{
Matrix[row][column] = rand.Next(1, 10);
}
}
}
}``````

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

Brute force approach:

``````public static int maxSum = Integer.MIN_VALUE;

public static void maxSum(int currentRow, int currentColumn, int rows, int currentSum, int[][] array) {

if (currentRow == rows) {
maxSum = Math.max(maxSum, currentSum);
return;
} else {
for (int i = currentColumn; i <= currentRow; i++) {
maxSum(currentRow + 1, i, rows, currentSum + array[currentRow][i], array);
}
}
}``````

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

If we need to print out only maximum weight, algorithm can be simplified as follows.

``````auto W = [](const vector<vector<int>>& data) {
int N = data.size();
vector<vector<int>> R(N+1, vector<int>(N+1, 0));
for (int i = N-1; i >= 0; --i) {
for (int j = i; j >= 0; --j) {
R[i][j] = data[i][j] + max(R[i+1][j], R[i+1][j+1]);
}
}
return R[0][0];
};``````

If we should print out the path, then R matrix may store the max cell too.

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

Solution using queues

``````#include <iostream>
#include <queue>

using namespace std;

#define SIZE 5

int GetMax(int arr[SIZE][SIZE]) {
queue<int> s1, s2;
queue<int> *p1 = nullptr, *p2 = nullptr;
int mx = 0;
s1.push(arr[0][0]);
for(int i = 1; i < SIZE; ++i) {
p1 = &s1;
p2 = &s2;
int count = p1->size();
if(count == 0)
swap(p1, p2);
count = p1->size();
for(int j = 0; j < count; ++j) {
int val = p1->front();
p1->pop();
int tmp;
tmp = val + arr[i][j];
mx = max(mx, tmp);
p2->push(tmp);
tmp = val + arr[i][j + 1];
mx = max(mx, tmp);
p2->push(tmp);
}
}
return mx;
}

int main() {
int arr[SIZE][SIZE] = {
{1,  0,  0,  0, 0},
{2,  1,  0,  0, 0},
{1,  3,  5,  0, 0},
{6,  10, 8,  4, 0},
{3,  5,  7,  1, 9}
};

cout << GetMax(arr);
return 0;
}``````

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

start from last row select the max element of the row ,now move upwards and look for the max of direct up element and diagonal up element ,,do till first row ....

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

start from last row select the max element of the row ,now move upwards and look for the max of direct up element and diagonal up element ,,do till first row ....

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

this approach would not work in the below case (changed the last element of the 4th row in the sample input)
4
2 9
15 1 3
16 92 41 300
8 142 6 4 8

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

select max element from all rows and then move according to rules upside and downside..

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

``````int Max(int a,int b)
{
if(a>b) return a;
return b;
}
void GetMax(int a[5][5], int i, int j,int n,int s,int *max)
{
if(i==n)
return;
if(i==n-1)
{
if(s+a[i][j]>*max)
*max= s+a[i][j];
}
GetMax(a,i+1,j,n,s+a[i][j],max);
GetMax(a,i+1,j+1,n,s+a[i][j],max);
}``````

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

int Max(int a,int b)
{
if(a>b) return a;
return b;
}
int GetMax(int a[5][5], int i, int j,int n,int s,int *max)
{
if(i==n-1)
{
return s+a[i][j];
}
return Max(GetMax(a,i+1,j,n,s+a[i][j],max),GetMax(a,i+1,j+1,n,s+a[i][j],max));
}

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

``````This program holds max path in f[] array.
i-row
j-col
n-num of rows
s = sum till now
*max - max till now
b[] - tmp array which holds current path
f[] - max path till now
void GetMax(int a[5][5], int i, int j,int n,int s,int *max,int b[],int f[])
{
if(i==n)
return;
b[i]=a[i][j];
if(i==n-1)
{
if(s+a[i][j]>*max)
{
*max= s+a[i][j];
for(int h=0;h<n;h++)
f[h]=b[h];
}
}
GetMax(a,i+1,j,n,s+a[i][j],max,b,f);
GetMax(a,i+1,j+1,n,s+a[i][j],max,b,f);
}``````

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.