Amazon Interview Question for Backend Developers


Country: United States




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

length = int(input())
flag = 0

arr = [[int(j) for j in input()] for i in range(length)]

print("Array begins here: \n")
for row in arr:
print(' '.join([str(elem) for elem in row]))


#Check for all elements on boundry are 1
for i in range(length):
if arr[0][i] != 1:
flag = 1
print("Issue in first row")

for i in range(length):
if arr[length-1][i] != 1:
flag = 1
print("Issue in last row")

for i in range(length):
if arr[i][0] != 1:
flag = 1
print("Issue in first Column")

for i in range(length):
if arr[i][length-1] != 1:
flag = 1
print("Issue in last column")


#Iterate inside and make it Zero
if flag != 1:
for i in range(1,length-1):
for j in range(1,length-1):
arr[i][j] = 0

print("Final Values in array are: \n")
for row in arr:
print(' '.join([str(elem) for elem in row]))

- Gaurav1wani March 15, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

For this problem, I am assuming we can modify the original matrix. In that case, scan through the islands matrix, and if we find an island that is surrounded by islands, remove it by setting it to 0. I present my solution in Python below. TC:- O(n*m) where n and m represents the number of rows and cols. SC:- O(1) since we are modifying the matrix in-place.

My solution:

def removeIslands(islandsMatrix):
    rows, cols = len(islandsMatrix), len(islandsMatrix[0])
    def isCoordinateWater(i, j):
        return 0 <= i < rows and 0 <= j < cols and islandsMatrix[i][j] == '0'

    for i, row in enumerate(islandsMatrix):
        for j, sq in enumerate(row):
            if sq == '1':
                coordinates = [(i+1,j), (i-1,j), (i,j+1), (i,j-1)]
                if all([isCoordinateWater(x, y) for x, y in coordinates]):
                    islandsMatrix[i][j] = '0'

    return islandsMatrix

Test Code:

islands = [
    ['1', '1', '1', '1', '1', '1'],
    ['1', '0', '0', '0', '0', '1'],
    ['1', '0', '0', '1', '0', '1'],
    ['1', '0', '0', '0', '0', '1'],
    ['1', '1', '1', '1', '1', '1']
]
from pprint import pprint
pprint(removeIslands(islands))
'''
Output: 
[
    ['1', '1', '1', '1', '1', '1'], 
    ['1', '0', '0', '0', '0', '1'], 
    ['1', '0', '0', '0', '0', '1'], 
    ['1', '0', '0', '0', '0', '1'], 
    ['1', '1', '1', '1', '1', '1']
]
'''

- prudent_programmer March 15, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

@prudent_programmer
What about this input ?
islands = [
['1', '1', '1', '1', '1','1' ,'1'],
['1', '0', '0', '0', '0', '0','1'],
['1', '0', '0', '1','1', '0', '1'],
['1', '0', '0', '0', '0', '1','1'],
['1', '1', '1', '1', '1', '1','1']
]
your code would generate this output:
islands = [
['1', '1', '1', '1', '1','1' ,'1'],
['1', '0', '0', '0', '0', '0','1'],
['1', '0', '0', '1','1', '0', '1'],
['1', '0', '0', '0', '0', '1','1'],
['1', '1', '1', '1', '1', '1','1']
]

but the correct output is:
islands = [
['1', '1', '1', '1', '1','1' ,'1'],
['1', '0', '0', '0', '0', '0','1'],
['1', '0', '0', '0','0', '0', '1'],
['1', '0', '0', '0', '0', '1','1'],
['1', '1', '1', '1', '1', '1','1']
]

- sbdul March 15, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

@sbdul Thank you so much.Nice catch. I didn't consider the edge cases and consider if the islands are stringed together or if they lie near the boundaries. I fixed my code and use DFS for searching through the grid and remove the islands as necessary. I have attached the rewritten code in Python below.

Solution:

def removeIslands(islandsMatrix):
  rows, cols = len(islandsMatrix), len(islandsMatrix[0])

  def dfs(i, j):
    # Check if the coordinate is a boundary
    if i in [0, rows-1] or j in [0, cols-1]:
      return True

    # Check if the coordinate is invalid
    if i < 0 or i >= rows \
            or j < 0 or j >= cols \
            or islandsMatrix[i][j] != '1':
      return False

    islandsMatrix[i][j] = '#' # Use '#' for marking
    coordinates = [(i+1,j), (i-1,j), (i,j+1), (i,j-1)]
    # If you find that all four sides are surrounded by water
    # then remove the islands by setting it to 0
    if not any(dfs(x, y) for x,y in coordinates):
      islandsMatrix[i][j] = '0'
    else: # Else, set it to 1
      islandsMatrix[i][j] = '1'

  for i, row in enumerate(islandsMatrix):
    for j, sq in enumerate(row):
        dfs(i, j)

  return islandsMatrix

Test code:

from pprint import pprint
islands1 = [
  ['1', '1', '1', '1', '1', '1', '1'],
  ['1', '0', '0', '0', '0', '0', '1'],
  ['1', '0', '0', '1', '1', '0', '1'],
  ['1', '0', '0', '0', '0', '1', '1'],
  ['1', '1', '1', '1', '1', '1', '1']
]
pprint(removeIslands(islands1))
print('--'* 20)
island2 = [
  ['1', '1', '1', '1', '1', '1', '1'],
  ['1', '0', '0', '0', '0', '0', '1'],
  ['1', '0', '1', '1', '0', '1', '1'],
  ['1', '0', '1', '0', '0', '0', '1'],
  ['1', '1', '0', '0', '0', '1', '1'],
  ['1', '1', '1', '1', '1', '1', '1']
]
pprint(removeIslands(island2))

Output:

[['1', '1', '1', '1', '1', '1', '1'],
 ['1', '0', '0', '0', '0', '0', '1'],
 ['1', '0', '0', '0', '0', '0', '1'],
 ['1', '0', '0', '0', '0', '1', '1'],
 ['1', '1', '1', '1', '1', '1', '1']]
----------------------------------------
[['1', '1', '1', '1', '1', '1', '1'],
 ['1', '0', '0', '0', '0', '0', '1'],
 ['1', '0', '0', '0', '0', '1', '1'],
 ['1', '0', '0', '0', '0', '0', '1'],
 ['1', '1', '0', '0', '0', '1', '1'],
 ['1', '1', '1', '1', '1', '1', '1']]

- prudent_programmer March 16, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

@prudent_programmer
Nice solution, another neat solution is to use union find data structure.
Start by connecting all boundary cells to a dummy node and then to iterate through the grid and for all the '1' cells check if one of their neighbors is connected to the dummy node, and if so, connect the current cell to the dummy node as well, and at the end iterate through the grid and set all '1' cells that aren't connected to the dummy node to '0'.

- sbdul March 16, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

static void RemoveComponents(int[,] board)
    {
        for (int c = 1; c < board.GetLength(1) - 1; c++){
            if (board[1, c] == 1)
                Traverse(board, 1, c);
            if (board[board.GetLength(0) - 2, c] == 1)
                Traverse(board, board.GetLength(0) - 2, c);
        }
        for (int r = 2; r < board.GetLength(0) - 2; r++){
            if (board[r, 1] == 1)
                Traverse(board, r, 1);
            if (board[r, board.GetLength(1) - 2] == 1)
                Traverse(board, r, board.GetLength(1) - 2);
        }
        for(int r = 1; r < board.GetLength(0) - 1; r++)
            for (int c = 1; c < board.GetLength(1) - 1; c++)
                if (board[r, c] == -1)
                    board[r, c] = 1;
                else if (board[r, c] == 1)
                    board[r, c] = 0;
    }

    static void Traverse(int[,] board, int row, int col)
    {
        board[row, col] = -1;
        for (int r = row - 1; r <= row + 1; r++)
            for(int c = col - 1; c <= col + 1; c++){
                if ((r == row && c == col) || r < 1 || r >= board.GetLength(0) - 1 || 
                    c < 1 || c >= board.GetLength(1) - 1)
                    continue;

                if(board[r, c] == 1)
                    Traverse(board, r, c);
            }
    }

- zuza March 16, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Launch a dfs from the boundary and mark all elements as '2'. Now, just traverse the matrix once again and clear out all remaining 1s while resetting '2's to '1's.

- Pj March 18, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

@sbdul. Great approach. Using union find sounds cool! :)

- prudent_programmer March 19, 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