## Microsoft Interview Question

SDE-3s**Team:**Office

**Country:**India

**Interview Type:**In-Person

Answer I suggested:

Represented 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.

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()
```

Can be solved using dynamic programming.

Create a matrix A of n + 1 rows and m + 2 columns.

n is the number of rows for the wall and m number of bricks in each row

Set all the element of the first row of A to be 1, this means water can flow from the top level

Set the first and the last column of A to 0 it means the water cannot flow from the sides of the wall

For each i in 2 to n+1

For each j in 2 to m

A[i][j] = A[i-1][j-1] | A[i-1][j] | A[i-1][j+1]

For each element in the last row, if it is 1 this means there is a flow to the ground from that brick.

Got it. Using dfs we don't need to visit all cells if we can find a single path where water can flow, the worst case complexity will be O(n^2), And in my solution, I need to all cells and avg complexity will be O(n^2). Apart from that any other comments on the solution provided by me ?

- gopi.komanduri June 12, 2018