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.
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
}
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))
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))
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);
queue.add(start);
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);
}
}
#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;
}
/*
* Click `Run` to execute the snippet below!
*/
import java.io.*;
import java.util.*;
/*
* To execute Java, please define "static void main" on a class
* named Solution.
*
* If you need more classes, simply define them inline.
*/
// A 2d array has 0 and 1 as values. In one flip, 0's are changed to 1 if and only if any of the neighbors (left, right, top, bottom) is 1. Return the total number of flips required to convert the whole grid to 1's
// [1 1 1 0]
// [0 1 0 0]
// [1 0 1 0]
// Queue : [00 , 01, 02 , 11 , 20 , 22 , null ] Ones
// zeros : 6
class Solution {
public int getTransformationNum(int[][]grid){
if(grid == null || grid.length == 0){
return 0;
}
int zeros = 0;
int count = 0;
int [][] directions = {{0 , 1} , {1 , 0} , {-1 , 0} , {0 , -1}};
Queue <int[]> queue = new LinkedList<>();
for(int i = 0 ; i < grid.length ; i++){
for(int j = 0 ; j < grid[0].length ; j++){
if(grid[i][j] == 0){
zeros ++;
}else if(grid[i][j] == 1){
queue.add(new int [] {i , j});
}
}
}
queue.add(null);
while(!queue.isEmpty()){
int [] arr = queue.poll();
if(arr == null && !queue.isEmpty()){
queue.add(null);
count ++;
continue;
}
if(arr == null){
continue;
}
for(int [] dir : directions){
int row = arr[0] + dir[0];
int col = arr[1] + dir[1];
if(row < grid.length && row >= 0 && col < grid[0].length && col >=0 && grid[row][col] == 0){
grid[row][col] = 1;
queue.add(new int[] {row , col});
zeros --;
}
}
if(zeros != 0 ){
return -1;
}
}
return count;
}
public static void main(String[] args) {
Solution s = new Solution();
//int [][] matrix = {{0 , 1 , 0 , 1} , {1,1,1,0} , {0 , 0 , 1 , 1} , {1, 0 , 0 ,1}};
int [][] matrix = {{0 , 1} , {1 , 0}};
System.out.println (s.getTransformationNum(matrix));
}
}
/*
* Click `Run` to execute the snippet below!
*/
import java.io.*;
import java.util.*;
/*
* To execute Java, please define "static void main" on a class
* named Solution.
*
* If you need more classes, simply define them inline.
*/
// A 2d array has 0 and 1 as values. In one flip, 0's are changed to 1 if and only if any of the neighbors (left, right, top, bottom) is 1. Return the total number of flips required to convert the whole grid to 1's
// [1 1 1 0]
// [0 1 0 0]
// [1 0 1 0]
// Queue : [00 , 01, 02 , 11 , 20 , 22 , null ] Ones
// zeros : 6
class Solution {
public int getTransformationNum(int[][]grid){
if(grid == null || grid.length == 0){
return 0;
}
int zeros = 0;
int count = 0;
int [][] directions = {{0 , 1} , {1 , 0} , {-1 , 0} , {0 , -1}};
Queue <int[]> queue = new LinkedList<>();
for(int i = 0 ; i < grid.length ; i++){
for(int j = 0 ; j < grid[0].length ; j++){
if(grid[i][j] == 0){
zeros ++;
}else if(grid[i][j] == 1){
queue.add(new int [] {i , j});
}
}
}
queue.add(null);
while(!queue.isEmpty()){
int [] arr = queue.poll();
if(arr == null && !queue.isEmpty()){
queue.add(null);
count ++;
continue;
}
if(arr == null){
continue;
}
for(int [] dir : directions){
int row = arr[0] + dir[0];
int col = arr[1] + dir[1];
if(row < grid.length && row >= 0 && col < grid[0].length && col >=0 && grid[row][col] == 0){
grid[row][col] = 1;
queue.add(new int[] {row , col});
zeros --;
}
}
if(zeros != 0 ){
return -1;
}
}
return count;
}
public static void main(String[] args) {
Solution s = new Solution();
//int [][] matrix = {{0 , 1 , 0 , 1} , {1,1,1,0} , {0 , 0 , 1 , 1} , {1, 0 , 0 ,1}};
int [][] matrix = {{0 , 1} , {1 , 0}};
System.out.println (s.getTransformationNum(matrix));
}
}
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