## Amazon Interview Question for SDETs

• 0

Country: United States
Interview Type: Written Test

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

this problem appears to be like ramanujan's partition.
for 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

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

``````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)
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
jj = j + k
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)``````

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

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)
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
jj = j + k
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)``````

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

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

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

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.

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.