Amazon Interview Question: You are given a n*n matrix of... | Glassdoor

Interview Question

Software Development Engineer In Test I (SDET) Interview Seattle, WA

You are given a n*n matrix of bits (1s and 0s) where

  1 represents land and 0 represents water. Adjacent 1s can be considered as joined together to form sort of island in water. Count the number of islands. Discuss complexity.
Tags:
complexity, technical writing
Answer

Interview Answer

2 Answers

2

int nCnt = 0;
int land = 0;
boolean bIsOne = false;
int a[rows][cloumns];
int i,j;
for(i = 0;i 1)
                   {
                          land ++;
                    }
                    nCnt = 0;
                    bIsOne = false;
            }
        }
    }
}

Pradnya on Feb 1, 2013
0

My runnable code is here. With the use of DFS, it is very straightforward!

public class Island{
    int[][] map;
    boolean[][] visited;
    int maxRow, maxCol;

    public Island(int [][] map){
        this.map = map;
        maxRow = map.length - 1;
        maxCol = map[0].length - 1;
        visited = new boolean[maxRow + 1][maxCol + 1];
    }

    public int islandCount(){
        int count = 0;

        for(int i = 0; i maxRow || j > maxCol) return;

        if(!visited[i][j] && map[i][j] == 1) {
            visited[i][j] = true;
            runDFS(i - 1, j);
            runDFS(i , j + 1);
            runDFS(i + 1, j);
            runDFS(i , j + 1);
        }
    }

public class questions{
    public static void main(String [] args){

        int [][] map = new int [][]{
                {1, 1, 1, 1, 0},
                {0, 1, 0, 1, 0},
                {0, 1, 1, 0, 1}
        };

        Island island = new Island(map);
        System.out.println(island.islandCount());
    }
}

Habib on Feb 13, 2016

Add Answers or Comments

To comment on this, Sign In or Sign Up.