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

- anonymous October 29, 2014 | Flag Reply
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)

- ramdomain October 29, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- ninhnnsoc October 30, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- CptSudoku April 14, 2015 | Flag
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;
	}

- gudujarlson October 29, 2014 | Flag Reply
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;
}

- Vova October 29, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- anonymous December 18, 2014 | Flag
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

Final answer:

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

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

- ninhnnsoc October 30, 2014 | Flag Reply
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]);


    }

- radhakrishna October 30, 2014 | Flag Reply
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;
}

- Anonymous October 31, 2014 | Flag Reply
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);
				}
				
			}
		}
	}
	
}

- Karthik November 03, 2014 | Flag Reply
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

- harshit.knit November 05, 2014 | Flag Reply
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;
}

- vipin kaushal November 05, 2014 | Flag Reply
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]);
                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);
                }
            }
        }
    }

- Pramod November 05, 2014 | Flag Reply
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]);
                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);
                }
            }
        }
    }

- pc November 05, 2014 | Flag Reply
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);
			}
		}
	}

- Anonymous November 28, 2014 | Flag Reply
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.

- anonymous December 18, 2014 | Flag Reply
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;
}

- rishab99999 April 09, 2015 | Flag Reply
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 ....

- jimmy October 29, 2014 | Flag Reply
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 ....

- jimmy October 29, 2014 | Flag Reply
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

- ramdomain October 29, 2014 | Flag
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..

- Anonymous October 29, 2014 | Flag
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);
}

- Chithra October 29, 2014 | Flag Reply
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));
}

- Chithra October 29, 2014 | Flag Reply
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);
}

- Chithra October 29, 2014 | 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