## Amazon Interview Question

SDETs**Country:**United States

**Interview Type:**Written Test

```
from collections import deque
dirs = [
[-1,0],
[1,0],
[0,-1],
[0,1],
]
def count_flips(board):
if not board:
return 0
seen = {}
candid = deque()
n, m = len(board), len(board[0])
for i in xrange(n):
for j in xrange(m):
if board[i][j] == 1:
seen[(i, j)] = 0
candid.append((i,j))
def is_on_board(i, j):
if i < 0 or j < 0 or i >= n or j >= m:
return False
return True
while candid:
i, j = candid.pop()
for k in dirs:
ii = i + k[0]
jj = j + k[1]
if is_on_board(ii, jj) and not board[ii][jj] and (ii, jj) not in seen:
seen[(ii, jj)] = seen[(i, j)] + 1
candid.append((ii,jj))
return max(seen.itervalues()) if seen else -1
a = [[0, 1],
[1, 0],
]
print count_flips(a)
```

It is a simple BFS:

```
from collections import deque
dirs = [
[-1,0],
[1,0],
[0,-1],
[0,1],
]
def count_flips(board):
if not board:
return 0
seen = {}
candid = deque()
n, m = len(board), len(board[0])
for i in xrange(n):
for j in xrange(m):
if board[i][j] == 1:
seen[(i, j)] = 0
candid.append((i,j))
def is_on_board(i, j):
if i < 0 or j < 0 or i >= n or j >= m:
return False
return True
while candid:
i, j = candid.pop()
for k in dirs:
ii = i + k[0]
jj = j + k[1]
if is_on_board(ii, jj) and not board[ii][jj] and (ii, jj) not in seen:
seen[(ii, jj)] = seen[(i, j)] + 1
candid.append((ii,jj))
return max(seen.itervalues()) if seen else -1
a = [[0, 1],
[1, 0],
]
print count_flips(a)
```

I'll do a brute force approach of calculating the number of flips but I'll cheat doing it in place.

```
int calculateNumberOfFlips(int[][] array) {
totalFlips = 0
lastFlip = 1
while(true) {
hasFlipped = false;
for(int i = 0; i < array.length; i++) {
for(int j = 0; i < array[i]; j++) {
int hasTop = hasVal(array, i -1, j, lastFlip);
int hasBottom = hasVal(array, i + 1, j, lastFlip);
int hasLeft = hasVal(array, i, j-1, lastFlip);
int hasRight = hasVal(array, i, j+1, lastFlip);
if(hasTop || hasBottom || hasLeft || hasRight) {
array[i][j] = lastFlip + 1;
hasFlipped = true;
}
}
}
if(!hasFlipped) break;
totalFlips++;
lastFlip++
}
bool isFull = checkIfFull(array)
cleanFlips(array)
return isFull ? totalFlips:-1; // Return -1 if it is not possible to make it full
}
bool hasVal(int[][] array, int i, int j, int lastFlip) {
/*
* I know this can be done in one line but this looks cleaner this way for all the onliner coders out there.
*/
if(i < 0) return false;
if (j < 0) return false;
if(i >= array.length) return false;
if(j >= array[i].length) return false;
if(array[i][j] > 0 && array[i][i] <= lastFlip) return true;
return false;
}
bool isFull(array) {
for(int i = 0; i < array.length; i++) {
for(int j = 0; j < array[i].length; j++) {
if(array[i][j] == 0) {
return false;
}
}
}
return true;
}
void cleanFlips(int[][] array) {
for(int i = 0; i < array.length; i++)
for(int j = 0; j < array[i].length; j++)
if(array[i][j] > 1)
array[i][j] = 0
}
```

Hi there,

Trying to get the worst case scenario (the most flips required) where the array has only one position with 1 and the rest filled with 0's.

In this scenario if iterate from position (0,0) to the (n-1)'th position (n-1,n-1) the flips required will be the addition of both the x and y coordinate and can be expressed as: 2(n-1).

So for a 3x3 matrix the flips are: 4

4x4: 6

....

9x9:16 and so on

In scenarios where the only 1 present is in other position rather than the last one then the flips required are still represented by the addition of both coordinate components (x,y) so no mather the order of the matrix if we iterate the matrix in order starting from (0,0) then the flips needed to fill the matrix with 1's are the addition of the coordinates x+y.

So if the 1 is in (1,1) then te amount of flips required are: 2

(2,2): 4

(3,1): 4

...

If there is more than one 1 then the flips needed could be calculated by searching the first 1 and then the last rule apply, the flips needed are described by the addition of the coordinate componentes x+y.

this problem appears to be like ramanujan's partition.

- aravind February 13, 2020for ex :

in a 3x3 matrix (9 cells)

if location (0,0) or (2,2) or (0,2) or (2,0) only one cell is 1 and rest all are 0

then no. of iterations : 4

which is same as 9 = 1 + 2+ 3+ 2+ 1 (+ sign in this expression indirectly indicates a flip )

if location (1,1) only one cell is 1 and rest all are 0

then no. of iterations : 2

which is same as 9 = 1+4+ 4

i cud not think more similar algo than this but i will wait for experts to provide answer