## 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

Hi, can you please share a kinda algorithm for the same? Will your approach work if we have more than one 1s in the matrix?

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

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

It should be {i, j = candid.popleft()} instead?

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

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.

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

const checkFlipCount = (matrix) => {
let count = 0
let parent = []
let children = []
let print = `matrix at \${count} flips\n\${matrix.join('\n')}`

matrix.forEach((array, i) => {
array.forEach((num, j) => {
if (num) parent.push([i, j])
});
});

while(parent.length) {
let curr = parent.pop()

if (curr[0] < matrix.length - 1) {
let b = [curr[0] + 1, curr[1]]
let bv = matrix[b[0]][b[1]]
bv ? null : children.push(b)
matrix[b[0]][b[1]] = 1
}
if (curr[0] > 0) {
let t = [curr[0] - 1, curr[1]]
let tv = matrix[t[0]][t[1]]
tv ? null : children.push(t)
matrix[t[0]][t[1]] = 1
}
if (curr[1] < matrix[0].length - 1) {
let r = [curr[0], curr[1] + 1]
let rv = matrix[r[0]][r[1]]
rv ? null : children.push(r)
matrix[r[0]][r[1]] = 1
}
if (curr[1] > 0) {
let l = [curr[0], curr[1] - 1]
let lv = matrix[l[0]][l[1]]
lv ? null : children.push(l)
matrix[l[0]][l[1]] = 1
}

if (parent.length === 0 && children.length !== 0) {
parent = [...children]
children = []
count++
print += `\n\nmatrix at \${count} flips\n\${matrix.join('\n')}`
}
}

console.log(print)
return count
}

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

mat = [[1, 0, 1, 0],[0, 0, 1, 0],[0, 0, 0, 0]]

def flip(mat):
r = len(mat)
c = len(mat[0])
neigh = []
count = 0
for i in range(r):
for j in range(c):
if mat[i][j] == 1:
if (i+1,j) not in neigh:
neigh.extend([(i+1,j)])
if (i-1,j) not in neigh:
neigh.extend([(i-1,j)])
if (i,j+1) not in neigh:
neigh.extend([(i,j+1)])
if (i,j-1) not in neigh:
neigh.extend([(i,j-1)])
for i in range(r):
for j in range(c):
if (i,j) in neigh and mat[i][j]==0:
count += 1
mat[i][j] = 1
return mat, count

print(flip(mat))

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

mat = [[1, 0, 1, 0],[0, 0, 1, 0],[0, 0, 0, 0]]

def flip(mat):
r = len(mat)
c = len(mat[0])
neigh = []
count = 0
for i in range(r):
for j in range(c):
if mat[i][j] == 1:
if (i+1,j) not in neigh:
neigh.extend([(i+1,j)])
if (i-1,j) not in neigh:
neigh.extend([(i-1,j)])
if (i,j+1) not in neigh:
neigh.extend([(i,j+1)])
if (i,j-1) not in neigh:
neigh.extend([(i,j-1)])
for i in range(r):
for j in range(c):
if (i,j) in neigh and mat[i][j]==0:
count += 1
mat[i][j] = 1
return mat, count

print(flip(mat))

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

find the distance of nearest 1 for every 0 using BFS. Maximum of this distance is the answer.

Assume a 4x4 matrix. All elements are 0's except (0,0). The farthest 0 which is at (3,3) will be set to 1 in 6th iteration. The flipping process will start at (0,0) and will take 6 iterations to reach (3,3).

import java.util.Random;
import java.util.ArrayDeque;

class Cell {
int r;
int c;
int d;

public Cell(int r, int c) {
if (r < 0 || c < 0) {
throw new IllegalArgumentException("invalid row and column for cell data");
}
this.r = r;
this.c = c;
this.d = 0;
}

public Cell(int r, int c, int d) {
this(r, c);
this.d = d;
}

public String toString() {
return String.format("%d %d", r, c);
}
}

public class HelloWorld{
private static final int[] nextR = {0, 0, -1, 1};
private static final int[] nextC = {-1, 1, 0, 0};

private static void printMatrix(int[][] mat) {
for (int r = 0; r < mat.length; ++r) {
for (int c = 0; c < mat[0].length; ++c) {
System.out.print(mat[r][c] + " ");
}
System.out.println("");
}
}

private static int[][] generateMatrix(int R, int C) {
if (R < 0 || C < 0) {
throw new IllegalArgumentException("Invalid R and C for generation of matrix");
}
int i = 1;
int[][] matrix = new int[R][C];
Random rand = new Random();
for (int r = 0; r < R; ++r) {
for (int c = 0; c < C; ++c) {
if (rand.nextBoolean() && i <= 1) {
matrix[r][c] = 1;
i++;
} else {
matrix[r][c] = 0;
}
}
}

return matrix;
}

private static boolean isValid(int r, int c, int R, int C) {
return (r >= 0) && (r < R) && (c >= 0) && (c < C);
}

private static Cell findValidCell(int[][] mat) {
for (int r = 0; r < mat.length; ++r) {
for (int c = 0; c < mat[0].length; ++c) {
if (mat[r][c] == 1) {
return new Cell(r, c);
}
}
}
return null;
}

private static boolean isOne(int[][] mat, Cell cell) {
return (mat[cell.r][cell.c] == 0);
}

private static int nearestOne(int[][] mat, int r, int c, int R, int C) {
int distance = 0;
ArrayDeque<Cell> queue = new ArrayDeque<>();
boolean[][] visited = new boolean[R][C];

Cell start = new Cell(r, c, 0);
visited[start.r][start.c] = true;

while (!queue.isEmpty()) {
Cell current = queue.remove();
if (mat[current.r][current.c] == 1) {
return current.d;
}

for (int i = 0; i < nextR.length; ++i) {
int rNext = current.r + nextR[i];
int cNext = current.c + nextC[i];

if (isValid(rNext, cNext, R, C) && !visited[rNext][cNext]) {
visited[rNext][cNext] = true;
queue.add(new Cell(rNext, cNext, current.d + 1));
}
}
}
return distance;
}

private static int numFlips(int[][] mat, int R, int C) {
int flips = 0;

for (int r = 0; r < R; ++r) {
for (int c = 0; c < C; ++c) {
if (mat[r][c] == 0) {
int distance = nearestOne(mat, r, c, R, C);
flips = Math.max(distance, flips);
}
}
}

return flips;
}

public static void main(String []args){
int R = 4;
int C = 4;
int[][] mat = generateMatrix(R, C);

printMatrix(mat);

int flips = numFlips(mat, R, C);
System.out.println("Flips : " + flips);
}
}

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

it seems to be rotten orange question

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

#include <stdio.h>
#define ROWS 2
#define COL 2

char arr[ROWS][COL];
char flip_id[ROWS][COL] = {0};

void get_input()
{
int i, j;
for( i =0; i < ROWS; i++)
{
for( j=0; j < COL; j++)
{
printf("Enter element no [%d][%d]:\n",i,j);
scanf("%d",&arr[i][j]);
}

}

}

void print_arr()
{
int i, j;
printf("Array is: \n");
for( i =0; i < ROWS; i++)
{
for( j=0; j < COL; j++)
{
printf("%d ",arr[i][j]);
}
printf("\n");

}
}

int all_flipped()
{
int i, j;
int status = 0;

for(i =0; i < ROWS; i++)
{
for( j=0; j < COL; j++)
{
if(arr[i][j] == 0)
return status;
}
}
status = 1;
return status;
}

int no_of_flips()
{
int i, j;
static int flip;
int m,n;
for(m =0; m < ROWS; m++)
{
for(n =0; n < COL; n++)
{
flip_id[m][n] = 0;
}
}
printf("Flip %d : \n",flip);
for(i = 0; i < ROWS; i++)
{
for(j = 0; j< COL; j++)
{
if(arr[i][j] == 1 && flip_id[i][j] != 1) {
/*Left index*/
if(i != 0) {
int left_index = i -1;
if(arr[left_index][j] != 1) {
arr[left_index][j] = 1;
flip_id[left_index][j] = 1;
}
}
/*Right index*/
int right_index = i + 1;
if(right_index < COL)
{
if(arr[right_index][j] != 1)
{
arr[right_index][j] = 1;
flip_id[right_index][j] = 1;
}
}
/*top index*/
int top_index = j - 1;
if(top_index >= 0)
{
if(arr[i][top_index] != 1)
{
arr[i][top_index] = 1;
flip_id[i][top_index] = 1;
}
}
/*bottom index*/
int bottom_index = j + 1;
if(bottom_index < COL)
{
if(arr[i][bottom_index] != 1)
{
arr[i][bottom_index] = 1;
flip_id[i][bottom_index] = 1;
}
}
flip_id[i][j] = 1;
}
}
}

print_arr();
print_flip_arr();
flip++;
if(all_flipped())
return flip;
else
{
no_of_flips();
}
}

int main()
{
printf("Hello World");
get_input();
print_arr();
int count = no_of_flips();
printf("No of flips = %d\n",count);
print_arr();
return 0;
}

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.