Microsoft Interview Question
SDE-3sTeam: 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