Microsoft Interview Question
Software Engineer / DevelopersCountry: India
Interview Type: Phone Interview
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)
/**
* 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;
}
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;
}
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
Final answer:
ANS = max(OPT[n][i]) for i = 1..n;
Can be implemented in O(n^2) time and space;
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]);
}
#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;
}
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);
}
}
}
}
}
# 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
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;
}
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]);
path.AddRange(path1List);
return path1 + Matrix[row][col];
} else
{
path.Add("Move to " +Matrix[row + 1][col + 1]);
path.AddRange(path2List);
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);
}
}
}
}
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]);
path.AddRange(path1List);
return path1 + Matrix[row][col];
} else
{
path.Add("Move to " +Matrix[row + 1][col + 1]);
path.AddRange(path2List);
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);
}
}
}
}
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);
}
}
}
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.
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;
}
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 ....
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
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);
}
Using DP:
- anonymous October 29, 2014opt[i][j]=max{opt[i+1][j], opt[i+1][j+1]}