Amazon Interview Question
SDE-2sCountry: India
Interview Type: Written Test
This will fail for all one or only one 0.
The following should work feel
boolean poolPresent()
{
int ones=0;
int zeroes=0;
boolean pool=true;
for (int i=0; i<r;i++)
{
for (int j=0;j<c;j++)
{
if ((i==0||i==(r-1)|| j==0||j==(c-1))&&a[i][j]!=1)//boundary conditions
return false;
else if ((a[i][j]==0)&& this.allNeigboursLand(i,j))// isolated 0
{
pool=false;
}
if (a[i][j]==1)ones++;
if (a[i][j]==0)zeroes++;
}
}
if (ones==r*c) //all ones
return false;
else if (zeroes!=1&&!pool) //isolated 0 and a pool
return false;
else return true;
}
It will work for both cases you mentioned( read corner case ) + non pool case should have two 0'.
Idea is nice but it might not work for 2 pairs of 2s separated by some 1s like
1 0 0 1 0 0 1
I believe this is related 2 number of graph compnents :)
int check(int a[][100],int i,int j)
{
int count = a[i-1][j] + a[i+1][j] + a[i][j-1] + a[i][j+1];
if(count<4)
return 1;
return 0;
}
void modify(int a[][100],int i,int j)
{
if(i<0 || i>=M || j<0 || j>=N || a[i][j]==1)
return;
a[i][j]=1;
modify(a,i-1,j);
modify(a,i+1,j);
modify(a,i,j-1);
modify(a,i,j+1);
}
int poolpresent(int a[][100])
{
int found=0;
int i,j;
for(j=0;j<N;j++)
{
for(i=0;i<M;i++)
{
if(a[i][j]==0)
{
found=1;
if(i==0 || j==0)
return 0;
if(check(a,i,j))
modify(a,i,j);
else
return 0;
}
}
}
return found;
}
Some clarifications would help:
a. Can we assume that the input will always be given a 5 by 4 matrix?
b. Would it be okay to assume that the 'outer' rows/columns will never have 0s?
c. What happens if there is a single zero in the center of the array? Will this be considered as a pool?
To me, this problem seems clearer if we explicitly specify that the goal is to determine if there is a _single_ pool in the matrix.
public class PoolOfZeros {
public static void main(String[] args) {
byte[][] array = {
{1,1,1,1,1},
{1,0,1,0,1},
{1,0,1,0,1},
{1,0,1,0,1},
{1,0,0,0,1},
{1,1,1,1,1}
};
boolean poolPresent = true;
boolean zeroFound = false;
if (!checkBorder(array)) {
System.out.println("Border not present.");
poolPresent = false;
} else {
for (int i = 1; i<array.length-1; i++) {
for (int j = 1; j < (array[i].length)-1; j++) {
if (array[i][j] == 0) {
// Found first 0 element;
zeroFound = true;
markZeroAndTraverse(array, i, j);
break;
}
}
if (zeroFound) {
break;
}
}
}
for (int i = 1; i<array.length-1; i++) {
for (int j = 1; j < array[i].length-1; j++) {
if (array[i][j] == 0) {
poolPresent = false;
}
}
}
System.out.println("Pool present: " + (poolPresent && zeroFound));
}
private static void markZeroAndTraverse(byte[][] array, int i, int j) {
if (array[i][j] == 0) {
array[i][j] = 2;
} else {
return;
}
markZeroAndTraverse(array,i-1,j);
markZeroAndTraverse(array,i+1,j);
markZeroAndTraverse(array,i,j-1);
markZeroAndTraverse(array,i,j+1);
}
private static boolean checkBorder(byte[][] array) {
for (int i = 0; i<array.length; i++) {
int colLength = array[i].length;
if (i == 0 || i == array.length-1) {
for (int j = 0; j<colLength; j++) {
if (array[i][j] != 1) {
return false;
}
}
} else {
if (array[i][0] != 1 || array[i][colLength-1] != 1) {
return false;
}
}
}
return true;
}
}
void reduce(int **a, int i, int j, int *m, int *n)
{
int k, l, c1, c2, c3, c4;
while(1)
{
if(i-1 && !a[i-1][j])
{
for(k = 0; k < *n; k++)
a[i][k] &= a[i-1][k];
for(k = i; k < *m; k++)
for(l = 0; l < *n; l++)
a[k-1][l] = a[k][l];
*m = *m - 1;
}
if(j-1 && !a[i][j-1])
{
for(k = 0; k < *m; k++)
a[k][j] &= a[k][j-1];
for(l = j; l < *n; l++)
for(k = 0; k < *m; k++)
a[k][l-1] = a[k][l];
*n = *n - 1;
}
if(i+1 < *m && !a[i+1][j])
{
for(k = 0; k < *n; k++)
a[i][k] &= a[i+1][k];
for(k = i+1; k < *m; k++)
for(l = 0; l < *n; l++)
a[k-1][l] = a[k][l];
*m = *m - 1;
}
if(j+1 < *n && !a[i][j+1])
{
for(k = 0; k < *m; k++)
a[k][j] &= a[k][j+1];
for(l = j+2; l < *n; l++)
for(k = 0; k < *m; k++)
a[k][l-1] = a[k][l];
*n = *n - 1;
}
c1 = (i-1)?a[i-1][j] : 1;
c2 = (j-1)?a[i][j-1] : 1;
c3 = (i+1 < *m)?a[i+1][j] : 1;
c4 = (j+1 < *n)?a[i][j+1] : 1;
if(c1 && c2 && c3 && c4)
return;
}
}
int check(int **a, int m, int n)
{
int i, j, flag;
flag = 1;
for(i = 0; i < m && flag; i++)
for(j = 0; j < n; j++)
if(!a[i][j])
{
reduce(a, i, j, &m, &n);
flag = 0;
break;
}
for(i = 0; i < m; i++)
for(j = 0; j < n; j++)
if(!a[i][j])
if(flag)
return 0;
else
flag = 1;
return flag;
}
#include<stdio.h>
int checkpool(int arr[4][4])
{
for(int i=0;i < (int)(sizeof(arr)/sizeof(int));i++)
{
if(arr[i][i]==arr[i][3]&&arr[i][i]==1)
return 1;
}
return 0;
}
int main()
{
int array[4][4] = {0,0,0,0,
1,1,1,0,
1,1,0,1,
1,0,1,1};
int answer = checkpool(array);
if(answer==1)
{
printf("There is pool");
}
else
{
printf("There is no pool");
}
}
Classic line fill algorithm: traverse the matrix until you find a 0 (i.e. water) then start filling the "reachable" water with a different color. Do a second traversal of the matrix to see if there are any uncoloured places left.
Possible optimizations:
1) After you have found a water drop and filled in the matrix, set a boolean foundWater = true. Carry on traversing and if uncolored water found again and foundWater==true, then you can terminate.
2) Use bytes instead of ints (I was too lazy to change the solution)
public void fillPoolWithColour(int[][] map, int x, int y, int colour){
if(x>=map.length){
return;
}
if(y>=map[x].length){
return;
}
if(map[x][y]==0){
map[x][y]=colour;
}else{
//we don't want to jump out of the pool
return;
}
//move in four directions
fillPoolWithColour(map,x-1,y,colour);
fillPoolWithColour(map,x,y-1,colour);
fillPoolWithColour(map,x+1,y,colour);
fillPoolWithColour(map,x,y+1,colour);
}
public void lookForWater(int[][] map){
for(int i=0;i<map.length;i++){
for(int j=0;j<map[i].length;j++){
if(map[i][j]==0){
fillPoolWithColour(map,i,j,-1);
return;
}
}
}
}
public boolean hasPool(int[][] map){
for(int i=0;i<map.length;i++){
for(int j=0;j<map[i].length;j++){
if(map[i][j]==0){
return false;
}
}
}
return true;
}
Updating the approach :
- Cerberuz February 09, 2014Count the number of connected components consisting of 0's. If count == 1 => pool, else non-pool.
Connected Component search can be performed in 4 directions only i.e. left-right-up-down.