## Microsoft Interview Question

SDE-3s**Team:**Office

**Country:**India

**Interview Type:**In-Person

Something like this, but you'd have to add for diagonals. This isn't optimised in any way

```
def recursiveCheck(matrix, n, m, i, j):
if (i + 1 >= n):
return True
if (i + 1 < n):
if (matrix[i + 1][j] == 'X'):
recursiveCheck(matrix, n, m, i + 1, j)
if (j - 1 > 0):
if (matrix[i][j - 1] == 'X'):
recursiveCheck(matrix, n, m, i, j - 1)
if (j + 1 < m):
if (matrix[i][j + 1] == 'X'):
recursiveCheck(matrix, n, m, i, j + 1)
else:
return False
def doCase():
# n, m = FP.readline().split()
# n, m = int(n), int(m)
n, m = 3, 3
line = ['XOX', 'XXO', 'OXO']
# line = FP.readline().split()
matrix = []
for i in range(n):
matrix.append(list(line[i]))
for i in range(n):
for j in range(m):
if (matrix[i][j] == 'X'):
if recursiveCheck(matrix, n, m, i, j):
print("Path")
return
print("No path")
doCase()
```

Something like this, adding diagonals is easy but I got bored of typing

```
def recursiveCheck(matrix, n, m, i, j):
if (i + 1 >= n):
return True
if (i + 1 < n):
if (matrix[i + 1][j] == 'X'):
recursiveCheck(matrix, n, m, i + 1, j)
if (j - 1 > 0):
if (matrix[i][j - 1] == 'X'):
recursiveCheck(matrix, n, m, i, j - 1)
if (j + 1 < m):
if (matrix[i][j + 1] == 'X'):
recursiveCheck(matrix, n, m, i, j + 1)
else:
return False
def doCase():
# n, m = FP.readline().split()
# n, m = int(n), int(m)
n, m = 3, 3
line = ['XOX', 'XXO', 'OXO']
# line = FP.readline().split()
matrix = []
for i in range(n):
matrix.append(list(line[i]))
for i in range(n):
for j in range(m):
if (matrix[i][j] == 'X'):
if recursiveCheck(matrix, n, m, i, j):
print("Path")
return
print("No path")
doCase()
```

Answer I suggested:

- gopi.komanduri June 11, 2018Represented the wall as 2x2 matrix. All opaque bricks are 1s and all Porus bricks are 0s.

algorithm:

we do using bottom up approach. from right most, bottom cell to top most left cell.

step 1: For any cell A[I][j], if that is 1, go to step 4. If that is 0, proceed to step 2

step 2: A[I][j] = product of (all elements around this cell from where water can pass.

A[I][j] = product (A[I-1][j] , A[I][j-1], A[I][j+1], A[I-1][j+1], A[I-1][j-1])

if value of A[I][j] == 1 go to step 4, else proceed to step 3.

step 3: A[I][j] = product (A[I+1,j-1], A[I+1,J],A[I+1,J+1].

step 4: repeat same to next cell,

Finally, loop through first row of the matrix, if there is any 0 , means there is a way water can travel till ground.