Microsoft Interview Question for SDE-3s


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 ?

- gopi.komanduri June 12, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

- gopi.komanduri June 11, 2018 | Flag Reply
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)

- Anonymous June 11, 2018 | Flag Reply
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 = 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()

- Jeff Bezos June 13, 2018 | Flag Reply
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 = 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()

- Jeff Bezos June 13, 2018 | Flag Reply
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.

- Nooreddin June 20, 2018 | Flag Reply
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;

- pnkcomm2u December 17, 2018 | Flag Reply


Add a Comment
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.

Learn More

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.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More