## Amazon Interview Question for Backend Developers

• 0

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]))

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']
]
'''``````

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

@prudent_programmer
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']
]

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']]``````

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

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);
}
}``````

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.

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

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

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.