## Microsoft Interview Question for SDE-3s

• 0

Team: Office
Country: India
Interview Type: In-Person

Comment hidden because of low score. Click to expand.
1
of 1 vote

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 ?

Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

Comment hidden because of low score. Click to expand.
0
of 0 vote

do a dfs, break when you reach the bottom.

To make the solution faster mark cells for visited (reachable or not to the bottom), and terminate that path if not reachable. O(n^2)

Comment hidden because of low score. Click to expand.
0
of 0 vote

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 = int(n), int(m)
n, m = 3, 3
line = ['XOX', 'XXO', 'OXO']
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()``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

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 = int(n), int(m)
n, m = 3, 3
line = ['XOX', 'XXO', 'OXO']
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()``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

Comment hidden because of low score. Click to expand.
0
of 0 vote

it is a question to find no of ways to reach from 1st row of matrix to
last row.

dp[i][j]=dp[i-1][j]+d[i][j-1]+dp[i-1][j-1]+d[i-1][j+1];

if(dp[n-1][j]>0)return true;
return false;

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.

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