## TATA Consultancy Services Interview Question

Software Developers**Country:**United States

**Interview Type:**Phone Interview

Take an example in question, I mean a 2D-array with dimension 4*4 (row=4, column=4) and we want find the Max sum path.

According to rule 1, so we start from the grid[4][0] location (fourth rows and first column), and its value is 4.

and go find the next element(cell) to reach the max sum path.

class Solution(object):

def maxPath(self,grid):

if not grid or not grid[0]:

return 0

res = 0

for i in xrange(len(grid)):

if grid[i][0] != -1:

sumRes = []

self.dfs(grid,i,0,0,sumRes)

res = max(res,max(sumRes))

return res

def dfs(self,grid,i,j,path,sumRes):

if j<0 or j==len(grid[0]) or i<0 or i==len(grid) or grid[i][j] == -1:

return

if j == len(grid[0])-1 and (i+1==len(grid) or grid[i+1][j] == -1) and (i-1<0 or grid[i-1][j] == -1):

sumRes.append(path+grid[i][j])

return

temp = grid[i][j]

grid[i][j] = -1

self.dfs(grid,i-1,j,path+temp,sumRes)

self.dfs(grid,i+1,j,path+temp,sumRes)

self.dfs(grid,i,j+1,path+temp,sumRes)

grid[i][j] = temp

return sumRes

```
class Solution(object):
def maxPath(self,grid):
if not grid or not grid[0]:
return 0
res = 0
for i in xrange(len(grid)):
if grid[i][0] != -1:
sumRes = []
self.dfs(grid,i,0,0,sumRes)
res = max(res,max(sumRes))
return res
def dfs(self,grid,i,j,path,sumRes):
if j<0 or j==len(grid[0]) or i<0 or i==len(grid) or grid[i][j] == -1:
return
if j == len(grid[0])-1 and (i+1==len(grid) or grid[i+1][j] == -1) and (i-1<0 or grid[i-1][j] == -1):
sumRes.append(path+grid[i][j])
return
temp = grid[i][j]
grid[i][j] = -1
self.dfs(grid,i-1,j,path+temp,sumRes)
self.dfs(grid,i+1,j,path+temp,sumRes)
self.dfs(grid,i,j+1,path+temp,sumRes)
grid[i][j] = temp
return sumRes
```

```
class Solution(object):
def maxPath(self,grid):
if not grid or not grid[0]:
return 0
res = 0
for i in xrange(len(grid)):
if grid[i][0] != -1:
sumRes = []
self.dfs(grid,i,0,0,sumRes)
res = max(res,max(sumRes))
return res
def dfs(self,grid,i,j,path,sumRes):
if j<0 or j==len(grid[0]) or i<0 or i==len(grid) or grid[i][j] == -1:
return
if j == len(grid[0])-1 and (i+1==len(grid) or grid[i+1][j] == -1) and (i-1<0 or grid[i-1][j] == -1):
sumRes.append(path+grid[i][j])
return
temp = grid[i][j]
grid[i][j] = -1
self.dfs(grid,i-1,j,path+temp,sumRes)
self.dfs(grid,i+1,j,path+temp,sumRes)
self.dfs(grid,i,j+1,path+temp,sumRes)
grid[i][j] = temp
return sumRes
```

```
class Solution(object):
def maxPath(self,grid):
if not grid or not grid[0]:
return 0
res = 0
for i in xrange(len(grid)):
if grid[i][0] != -1:
sumRes = []
self.dfs(grid,i,0,0,sumRes)
res = max(res,max(sumRes))
return res
def dfs(self,grid,i,j,path,sumRes):
if j<0 or j==len(grid[0]) or i<0 or i==len(grid) or grid[i][j] == -1:
return
if j == len(grid[0])-1 and (i+1==len(grid) or grid[i+1][j] == -1) and (i-1<0 or grid[i-1][j] == -1):
sumRes.append(path+grid[i][j])
return
temp = grid[i][j]
grid[i][j] = -1
self.dfs(grid,i-1,j,path+temp,sumRes)
self.dfs(grid,i+1,j,path+temp,sumRes)
self.dfs(grid,i,j+1,path+temp,sumRes)
grid[i][j] = temp
return sumRes
```

import java.lang.*;

import java.util.*;

public class MainClass {

public static void main(String[] args) {

@SuppressWarnings("resource")

Scanner rowDimension = new Scanner(System.in);

System.out.print("Enter the number of rows: ");

int firstInput = rowDimension.nextInt();

@SuppressWarnings("resource")

Scanner columnDimension = new Scanner(System.in);

System.out.print("Enter the number of columns: ");

int secondInput = columnDimension.nextInt();

//Input two number to generate 2D Array

Integer [][] array = new Integer[firstInput][secondInput];

//The purpose of the array is check the wall (cell value = -1)

boolean [][] visited = new boolean[firstInput][secondInput];

//Use Math.random() to generate the cell of the array

int[][] randomTable = new int[firstInput][secondInput];

for (int row = 0; row < firstInput; row++) {

for (int column = 0; column < secondInput; column++) {

// multiply by 1000000 to get a number between 0 and 99999

randomTable[row][column] = (int)(Math.random() * 1000000 -1);

System.out.print(randomTable[row][column] + " ");

}

System.out.println();

}

//Start form the left-down location of grid

int i = firstInput-1, j = 0;

visited[i][j] = true;

double sum = array[i][j];

while(true)

{

int max = -1;

int maxi = 0, maxj = 0;

//Case1 : choose path: UP

if(i-1 >= 0 && i-1<= firstInput-1 && j>=0 && j<= secondInput-1 && array[i-1][j] != null && array[i-1][j]>max && !visited[i-1][j])

{

max = array[i-1][j];

maxi = i-1;

maxj = j;

}

//Case2 : choose path: Down

if(i+1 >= 0 && i+1<= firstInput-1 && j>=0 && j<= secondInput-1 &&array[i+1][j] != null && array[i+1][j]>max && !visited[i+1][j])

{

max = array[i+1][j];

maxi = i+1;

maxj = j;

}

//Case3 : choose path: Right

if(i >= 0 && i<= firstInput-1 && j+1>=0 && j+1<= secondInput-1 && array[i][j+1] != null && array[i][j+1]>max && !visited[i][j+1])

{

max = array[i][j+1];

maxi = i;

maxj = j+1;

}

i = maxi;

j = maxj;

visited[i][j] = true;

sum += max;

//To the destination : Right-Up location of the grid

if(i == 0 && j == secondInput-1)

break;

}

System.out.println(sum);

}

}

/*Hello, Ziqiyang88,

I follow your pseudo code for reference, sorry I am very new in Java.

Here is my code, and there is a bug in my code.

"Exception in thread "main" java.lang.NullPointerException"

If you are available, would you please take a look my code? Thank you:)*/

I didn't understood the question nor the example output they showed. It's a 2-D array with 4 grids? and movements are not clear to me.

- Denis March 12, 2016