Amazon Interview Question for SDE-2s


Country: India
Interview Type: Written Test




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

Updating the approach :
Count 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.

- Cerberuz February 09, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Jainam Shah February 09, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

It will work for both cases you mentioned( read corner case ) + non pool case should have two 0'.

- Cerberuz February 10, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Anonymous February 10, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

yep, you are right :)

- Cerberuz February 10, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- Nitin February 10, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

- david.p.waters February 10, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- Lakshmi February 10, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- Anonymous February 11, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#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");
}
}

- Monis Majeed February 15, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- Vulkum February 15, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Method hasPool() doesn't call any other method or gets called.

- smallville March 01, 2014 | Flag
Comment hidden because of low score. Click to expand.


Add a Comment
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.

Learn More

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.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More