Amazon Interview Question Software Developers
Country: India
Interview Type: In-Person
public class NumberOfIlands {
public int solutionUsingDFS(int[][] matrix){
boolean[][] visited = new boolean[matrix.length][matrix[0].length];
int count = 0;
for (int i = 0; i < matrix.length; i++) {
for (int j = 0; j < matrix[0].length; j++) {
if(matrix[i][j] == 1 && !visited[i][j] ){
doDFS(matrix, visited, i, j);
count++;
}
}
}
return count;
}
public void doDFS(int[][] matrix, boolean[][] visited, int i, int j){
if(!isSafe(matrix, visited, i, j)){
return;
}
visited[i][j] = true;
doDFS(matrix, visited, i, j-1);
doDFS(matrix, visited, i, j+1);
doDFS(matrix, visited, i-1, j);
doDFS(matrix, visited, i+1, j);
}
public boolean isSafe(int[][] matrix, boolean[][] visited, int i, int j){
if(i < 0 || i >= matrix.length || j <0 || j >= matrix[0].length || visited[i][j] || matrix[i][j] == 0)
return false;
else
return true;
}
/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
NumberOfIlands obj = new NumberOfIlands();
int[][] matrix = {{1, 1, 1, 0, 1},
{1, 1, 1, 0, 0},
{0, 0, 0, 1, 1},
{1, 0, 0, 1, 0}};
System.out.println("row length" +matrix.length);
System.out.println("column length" +matrix[0].length);
int numberOfIsland = obj.solutionUsingDFS(matrix);
System.out.println("Number of Islands: "+numberOfIsland);
}
}
My on-paper solution is almost identical, however, if you simply use an int array as the input, and convert the 1 to a 2 (for example), then you can just maintain the 'visited' property that way. You don't need the extra visited array O(nxm) space saving.
Your if statement would simply become
if(arr[i][j] == 1) { //do work; }
We should be able to 'bleed out' when we find the start of an island, and mark as seen.
public int findIslands(int[][] array) {
if (array == null) {
return 0;
}
int islands = 0;
for (int r = 0; r < array.length; r++) {
for (int c = 0; c < array[r].length; c++) {
if (array[r][c] == 1) {
discoverIsland(array, r, c);
islands++;
}
}
}
return islands;
}
public void discoverIsland(int[][] array, int r, int c) {
// Verify bounds
if (r < 0 || r >= array.length || c < 0 || c >= array[r].length) {
return;
}
if (array[r][c] == 1) {
array[r][c] = -1;
} else {
return;
}
discoverIsland(array, r-1, c);
discoverIsland(array, r+1, c);
discoverIsland(array, r, c-1);
discoverIsland(array, r, c+1);
}
If you consider diagonal elements are connected, then solution of given matrix will be 3.
[1,2] is connected with [2,3] forming an island of eight 1s.
below is a solution in JavaScript.
function getIslands(pMatrix){
console.log("start");
var stack = [];
var visited = [];
var islands = 0;
for(var i=0;i<pMatrix[0].length;i++)
visited[i] = [];
function pushToStack(i,j){
if(pMatrix[i])
{
if(pMatrix[i][j] === undefined)
return;
if(visited[i][j])
return;
visited[i][j] = 1;
if(pMatrix[i][j] === 1)
stack.push({i,j});
}
}
function stackNeighbors(i,j){
pushToStack(i-1,j-1);
pushToStack(i-1,j);
pushToStack(i-1,j+1);
pushToStack(i,j-1);
pushToStack(i,j);
pushToStack(i,j+1);
pushToStack(i+1,j-1);
pushToStack(i+1,j);
pushToStack(i+1,j+1);
}
function visitIsland(){
while(stack.length > 0) {
var index = stack.pop();
stackNeighbors(index.i,index.j);
}
islands ++;
}
for(var i=0;i<pMatrix.length;i++) {
for(var j=0;j<pMatrix[i].length;j++) {
if(visited[i][j])
continue;
if(pMatrix[i][j] === 1){
stackNeighbors(i,j);
}
if(stack.length > 0)
visitIsland();
}
}
return islands;
}
public class P2 {
private static int ROWS, COLUMNS;
private static final int[][] map = { { 0, 1, 1, 0, 1 }, { 1, 1, 1, 0, 0 },
{ 0, 0, 0, 1, 1 }, { 1, 0, 0, 1, 0 } };
private static void mark(int r, int c) {
if (map[r][c] == 0) { // base case
return;
} else {
int[] dr = { 0, 0, 1, -1 };
int[] dc = { -1, 1, 0, 0 };
for (int i = 0; i < dr.length; i++) {
if (r + dr[i] >= 0 && r + dr[i] < ROWS && c + dc[i] >= 0
&& c + dc[i] < COLUMNS) {
map[r][c] = 0;
mark(r + dr[i], c + dc[i]);
}
}
}
}
public static void main(String[] args) {
int cc = 0;
ROWS = 4;
COLUMNS = 5;
for (int i = 0; i < map.length; i++) {
for (int j = 0; j < map[i].length; j++) {
if (map[i][j] == 1) {
mark(i, j);
cc++;
}
}
}
System.out.println(cc);
}
}
public class DiscoverIslands {
int[][] matrix;
public DiscoverIslands(int[][] matrix) {
this.matrix = matrix;
}
public DiscoverIslands(String filename) {
String line;
List<int[]> l = new ArrayList<int[]>();
try (BufferedReader rdr = new BufferedReader(new FileReader(filename))) {
while ((line = rdr.readLine()) != null) {
l.add(parseLine(line));
}
}
catch (IOException ioe) {
System.err.println("error: " + ioe);
return;
}
this.matrix = new int[l.size()][];
for ( int i = 0; i < this.matrix.length; ++i ) {
this.matrix[i] = l.get(i);
}
}
private class Position {
int row;
int col;
Position(int row, int col) {
this.row = row;
this.col = col;
}
public boolean equals(Object obj) {
if ( !(obj instanceof Position) ) return false;
Position other = (Position) obj;
return this.row == other.row && this.col == other.col;
}
public int hashCode() {
return this.row + this.col * matrix[this.row].length;
}
Position getDown() {
return (this.row + 1) >= matrix.length ? null : new Position(
this.row + 1, this.col);
}
Position getUp() {
return (this.row == 0) ? null
: new Position(this.row - 1, this.col);
}
Position getLeft() {
return this.col == 0 ? null : new Position(this.row, this.col - 1);
}
Position getRight() {
return (this.col + 1) >= matrix[this.row].length ? null
: new Position(this.row, this.col + 1);
}
public List<Position> getAdjancyList() {
List<Position> l = new ArrayList<Position>();
Position right = getRight();
if (isSet(right))
l.add(right);
Position up = getUp();
if (isSet(up))
l.add(up);
Position left = getLeft();
if (isSet(left))
l.add(left);
Position down = getDown();
if (isSet(down))
l.add(down);
return l;
}
public String toString() {
return this.row + ":" + this.col;
}
}
int[] parseLine(String line) {
String[] row = line.split("\\s");
int rowInt[] = new int[row.length];
for( int i =0; i < row.length; ++i ) {
rowInt[i] = Integer.parseInt(row[i].trim());
}
return rowInt;
}
boolean isSet(Position p) {
return (p != null) && (matrix[p.row][p.col] == 1);
}
void exploreIsland(Position p, Set<Position> visited) {
visited.add(p);
for (Position adj : p.getAdjancyList()) {
if (!visited.contains(adj)) {
exploreIsland(adj, visited);
}
}
}
public int getIslands() {
Set<Position> visited = new HashSet<Position>();
int islands = 0;
for (int row = 0; row < matrix.length; ++row) {
for (int col = 0; col < this.matrix[row].length; ++col ) {
if (matrix[row][col] == 1) {
Position p = new Position(row, col);
if (!visited.contains(p)) {
exploreIsland(p, visited);
++islands;
}
}
}
}
return islands;
}
public static void main(String[] args) {
String fileName = args[0];
DiscoverIslands d = new DiscoverIslands(fileName);
System.err.println("islands = " + d.getIslands());
}
}
a = [[ 0,1, 1, 0, 1 ], [ 1, 1, 1, 0, 0 ], [ 0, 0, 0, 1, 1 ], [ 1, 0, 0, 1, 0 ]]
nx = len(a)
ny = len(a[0])
def landscape(x, y):
if x < 0 or x >= nx or y < 0 or y >= ny:
return 0
if a[x][y] == 0:
return 0
a[x][y] = 0
landscape(x+1, y)
landscape(x, y+1)
landscape(x-1, y)
landscape(x, y-1)
return 1
z = 0
for x in range(nx):
for y in range(ny):
print(x)
print(y)
z = z + landscape(x, y)
print('Answer:' + str(z))
a = [[ 0,1, 1, 0, 1 ], [ 1, 1, 1, 0, 0 ], [ 0, 0, 0, 1, 1 ], [ 1, 0, 0, 1, 0 ]]
nx = len(a)
ny = len(a[0])
def landscape(x, y):
if x < 0 or x >= nx or y < 0 or y >= ny:
return 0
if a[x][y] == 0:
return 0
a[x][y] = 0
landscape(x+1, y)
landscape(x, y+1)
landscape(x-1, y)
landscape(x, y-1)
return 1
z = 0
for x in range(nx):
for y in range(ny):
print(x)
print(y)
z = z + landscape(x, y)
print('Answer:' + str(z))
a = [[ 0,1, 1, 0, 1 ], [ 1, 1, 1, 0, 0 ], [ 0, 0, 0, 1, 1 ], [ 1, 0, 0, 1, 0 ]]
nx = len(a)
ny = len(a[0])
def landscape(x, y):
if x < 0 or x >= nx or y < 0 or y >= ny:
return 0
if a[x][y] == 0:
return 0
a[x][y] = 0
landscape(x+1, y)
landscape(x, y+1)
landscape(x-1, y)
landscape(x, y-1)
return 1
z = 0
for x in range(nx):
for y in range(ny):
print(x)
print(y)
z = z + landscape(x, y)
print('Answer:' + str(z))
#include<stdio.h>
int iCnt;
int Find(int arr[5][5], int i, int j, int log[5][5])
{
if( !(i>-1 && j>-1 && i<5 && j<5 && !log[i][j] && arr[i][j] ))
return 0;
log[i][j] = 1;
Find(arr, i+1, j, log);
Find(arr, i, j+1, log);
Find(arr, i-1, j, log);
Find(arr, i, j-1, log);
iCnt++;
return 0;
}
int main()
{
int arr[][5]={ {0,1,1,0,1},
{1,1,1,0,0},
{0,0,0,1,1},
{0,0,0,1,0},
{1,0,0,1,0}
};
int log[5][5] = {0};
int i=0,j=2, Islands= 0;
for(i=0; i<5; i++)
for(j=0; j<5; j++)
if(arr[i][j] && !log[i][j]){
Find(arr, i, j, log);
if(iCnt) Islands++;
printf("Sea shore count: %d\n", iCnt);
iCnt = 0;
}
printf("Maximum possibilities %d\n", Islands);
return 0;
}
#include<stdio.h>
int iCnt;
int Find(int arr[5][5], int i, int j, int log[5][5])
{
if( !(i>-1 && j>-1 && i<5 && j<5 && !log[i][j] && arr[i][j] ))
return 0;
log[i][j] = 1;
Find(arr, i+1, j, log);
Find(arr, i, j+1, log);
Find(arr, i-1, j, log);
Find(arr, i, j-1, log);
iCnt++;
return 0;
}
int main()
{
int arr[][5]={ {0,1,1,0,1},
{1,1,1,0,0},
{0,0,0,1,1},
{0,0,0,1,0},
{1,0,0,1,0}
};
int log[5][5] = {0};
int i=0,j=2, Islands= 0;
for(i=0; i<5; i++)
for(j=0; j<5; j++)
if(arr[i][j] && !log[i][j]){
Find(arr, i, j, log);
if(iCnt) Islands++;
printf("Sea shore count: %d\n", iCnt);
iCnt = 0;
}
printf("Maximum possibilities %d\n", Islands);
return 0;
}
If this question is including diagonal cases like the description above, the correct answer of that example above should be 3, not 4.
#include <stdio.h>
#define MAX_X 4
#define MAX_Y 5
#define MAX_MEMO 20
void main(){
int i, j=0, k=0, x, y, landnum=0, findflag=1, jm=0;
int memo_x[MAX_MEMO] = { 0, };
int memo_y[MAX_MEMO] = { 0, };
int memo_d[MAX_MEMO] = { 0, };
int land[MAX_X][MAX_Y] = { { 1, 0, 1, 0, 1 },
{ 0, 1, 0, 1, 0 },
{ 1, 0, 1, 0, 0 },
{ 1, 0, 1, 0, 1 } };
x = 0, y = 0;
for (i = 0;;i++){
if (land[x][y] >= 1){
if (findflag == 1){
memo_x[k] = x;
memo_y[k] = y;
memo_d[k] = jm;
jm = 0;
}
else{
jm = memo_d[k+1] + 1;
}
for (j = jm; j < 8; j++){
if (j == 0){
if (x == 0){
findflag = 0;
continue;
}
else {
if (land[x - 1][y] == 1){
land[x][y] = 2;
x = x - 1;
findflag = 1;
k++;
break;
}
else{
findflag = 0;
continue;
}
}
}
if (j == 1){
if ((x == 0)||(y==(MAX_Y-1))){
findflag = 0;
continue;
}
else {
if (land[x - 1][y+1] == 1){
land[x][y] = 2;
x = x - 1;
y = y + 1;
findflag = 1;
k++;
break;
}
else{
findflag = 0;
continue;
}
}
}
if (j == 2){
if (y == (MAX_Y-1)){
findflag = 0;
continue;
}
else {
if (land[x][y+1] == 1){
land[x][y] = 2;
y = y + 1;
findflag = 1;
k++;
break;
}
else{
findflag = 0;
continue;
}
}
}
if (j == 3){
if ((x == (MAX_X-1)) || (y == (MAX_Y-1))){
findflag = 0;
continue;
}
else {
if (land[x + 1][y + 1] == 1){
land[x][y] = 2;
x = x + 1;
y = y + 1;
findflag = 1;
k++;
break;
}
else{
findflag = 0;
continue;
}
}
}
if (j == 4){
if (x == (MAX_X-1)){
findflag = 0;
continue;
}
else {
if (land[x + 1][y] == 1){
land[x][y] = 2;
x = x + 1;
findflag = 1;
k++;
break;
}
else{
findflag = 0;
continue;
}
}
}
if (j == 5){
if ((x == (MAX_X-1)) || (y == 0)){
findflag = 0;
continue;
}
else {
if (land[x + 1][y-1] == 1){
land[x][y] = 2;
x = x + 1;
y = y - 1;
findflag = 1;
k++;
break;
}
else{
findflag = 0;
continue;
}
}
}
if (j == 6){
if (y == 0){
findflag = 0;
continue;
}
else {
if (land[x][y-1] == 1){
land[x][y] = 2;
y = y - 1;
findflag = 1;
k++;
break;
}
else{
findflag = 0;
continue;
}
}
}
if (j == 7){
if ((x == 0) || (y == 0)){
findflag = 0;
continue;
}
else {
if (land[x - 1][y - 1] == 1){
land[x][y] = 2;
x = x - 1;
y = y - 1;
findflag = 1;
k++;
break;
}
else{
findflag = 0;
continue;
}
}
}
}
jm = j;
if (findflag == 0){
land[x][y] = 0;
if (k == 0){
jm = 0;
landnum++;
}
else{
k--;
x = memo_x[k];
y = memo_y[k];
jm = memo_d[k];
}
}
}
else{
if (k == 0){
if ((y + 1) == MAX_Y){
if ((x + 1) == MAX_X){
break;
}
else {
y = 0;
x++;
}
}
else y++;
}
}
}
printf("%d\n", landnum);
return;
}
public int findNumberOfIslands(int array[][]){
int islands = 0;
if(array != null && array.length > 0 && array[0].length > 0){
int row = array.length, col = array[0].length;
int island[][] = new int[row][col];
int checker[][] = {{0,-1},{-1,-1},{-1,0},{-1,1}};
for(int i = 0 ; i < row ; i++){
for(int j = 0 ; j < col ; j++){
if(array[i][j] == 1){
boolean formsIsland = true;
for(int check = 0 ; check < checker.length ; check++){
int checkI = i + checker[check][0]; int checkJ = j + checker[check][1];
if(checkI >= 0 && checkI < row && checkJ >= 0 && checkJ < col && array[checkI][checkJ] == 1){
if(island[i][j] == 0){
island[i][j] = island[checkI][checkJ];
}
else{
if(island[i][j] != island[checkI][checkJ])
islands--;
}
formsIsland = false;
}
}
if(formsIsland){
island[i][j] = ++islands;
}
}
}
}
}
return islands;
}
public int findNumberOfIslands(int array[][]){
int islands = 0;
if(array != null && array.length > 0 && array[0].length > 0){
int row = array.length, col = array[0].length;
int island[][] = new int[row][col];
int checker[][] = {{0,-1},{-1,-1},{-1,0},{-1,1}};
for(int i = 0 ; i < row ; i++){
for(int j = 0 ; j < col ; j++){
if(array[i][j] == 1){
boolean formsIsland = true;
for(int check = 0 ; check < checker.length ; check++){
int checkI = i + checker[check][0]; int checkJ = j + checker[check][1];
if(checkI >= 0 && checkI < row && checkJ >= 0 && checkJ < col && array[checkI][checkJ] == 1){
if(island[i][j] == 0){
island[i][j] = island[checkI][checkJ];
}
else{
if(island[i][j] != island[checkI][checkJ])
islands--;
}
formsIsland = false;
}
}
if(formsIsland){
island[i][j] = ++islands;
}
}
}
}
}
return islands;
}
The goal is to count a number of connected components in a graph. The problem can be solved by BFS or DFS. Let consider a BFS solution. For simplicity, let assume that the land is represented as a 'boolean[][] map' array and let assume that we can modify it. The solution may look like this:
Initiate a counter to zero
(i) Start at the top left corner of the map, find a land element ('true') and put its coordinates in a queue.
(ii) Dequeue an element and unmark it in the map as 'false'
(iii) Add its adjacent land neighbours to the queue
(iv) If the queue is not empty go to (ii) otherwise increment counter and continue with (i);
Return counter
A sample code is shown below:
- autoboli July 17, 2015public class Components{ public static int count(boolean[][] map) { int M = map.length; int N = map[0].length; int cnt = 0; for (int i=0; i<M; i++) for (int j=0; j<N; j++) if(map[i][j]) { visit(new Coord(i,j)); cnt++; } return cnt; } private static visit(boolean[][] map, Coord curr) { Queue<Coord> q = new Queue<Coord>(); q.add(curr); do { curr = q.remove(); map[curr.i][curr.j] = 0; for (c : adj(curr)) q.add(c); } while(!q.isempty()); return; } private static Iterable<Coord> adj(boolean[][] map, Coord curr) { int M = map.length; int N = map[0].length; LinkedList<Coord> lst = new LinkedList<Coord>(); for (int i = curr.i-1; i <= curr.i+1; i++) for (int j = curr.j-1; j <= curr.j+1; j++) if (i>=0 && i<M && j>=0 && j<N && map[i][j]) lst.add(new Coord(i,j)); return lst; } }