## Amazon Interview Question for Software Engineer Interns

Country: United States
Interview Type: In-Person

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

Assumptions : land and water space is represented as a matrix with m rows and n columns.
matrix[i][j] = 'x' represents land and matrix [i][j] = ' ' (space) represents water.

``````//visited matrix keeps track of which vertices are visited
bool ** visited;

// count number of islands
int numIslands = 0;

// function to mark connected islands parts as visited.
void exploreConnected( int i, int j);

int main (int argc, char ** argv){
int m = 100; // or take input from user
int n = 200; // or take input from user

// initialize first level of visited matrix - no need of calloc here.
visited = (bool **) malloc( m, sizeof(bool *) );
if( visited == NULL ) return -1;

// initialize second level of visited matrix - should be zeroed
for( int i = 0; i < m; i++ ){
visited[i] = (bool *) calloc( n, sizeof(bool) );
if(visited[i] == NULL) return -1;
}

// traverse nodes in row major fashion
for( int i = 0; i < m; i++){
for(int j = 0; j < n; j++){
// do not process a node if it is not island or processed already
if( matrix[i][j] == ' ' || visited[i][j] == true)
continue;
// we have found a new land!
numIslands++;

// now explore new land.
exploreConnected( i, j );
}
}

printf( "Num of islands = %d\n", numIslands );
}

void exploreConnected( int i, int j ){
visited[i][j] = true;

// check and explore right node in the same row.
if( j < n-1 && matrix[i][j+1] == 'x' && visited[i][j+1] == false)
exploreConnected( i, j+1 );

// check and explore lower left node
if( i < m-1 && j > 0 && matrix[i+1][j-1] == 'x' && visited[i+1][j-1] == false )
exploreConnected( i+1, j-1 );

// check and explore lower node
if( i < m-1 && matrix[i+1][j] =='x' && visited[i+1][j] == false)
exploreConnected( i+1, j );

// check and explore lower right node
if( i < m-1 && j < n-1 && matrix[i+1][j+1] == 'x' && visited[i+1][j+1] == false)
exploreConnected( i+1, j+1 );
}``````

As the for loop in the main function goes in row major order, we only need to check four adjacent nodes instead of all 8.

Time complexity : O(m*n)
Space complexity : O(m*n)

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

``````class Node {
int iIndex;
int jIndex;
public Node(int iIndex, int jIndex) {
super();
this.iIndex = iIndex;
this.jIndex = jIndex;
}
public int getiIndex() {
return iIndex;
}
public void setiIndex(int iIndex) {
this.iIndex = iIndex;
}
public int getjIndex() {
return jIndex;
}
public void setjIndex(int jIndex) {
this.jIndex = jIndex;
}
public Node() {
super();
}
}
public int findNumberOfIslands(boolean[][] islands) {
boolean[][] visited= new boolean[islands.length][islands[0].length];
for(boolean row[]:visited)
Arrays.fill(row, false);
int count = 0;
for(int i=0; i < islands.length;i++) {
for(int j=0; j < islands[0].length;j++) {
if(islands[i][j] && !visited[i][j]) {
visitAdjacentPlaces(islands, visited, i, j);
count++;
}
}
}
return count;
}

public void visitAdjacentPlaces(boolean[][] islands, boolean[][] visited, int i, int j) {
Queue<Node> queue = new LinkedList<Node>();
visited[i][j] = true;
queue.add(new Node(i,j));
while(!queue.isEmpty()) {
Node node = queue.poll();
int currenti = node.getiIndex();
int currentj = node.getjIndex();
if(currenti+1 < islands.length && islands[currenti+1][currentj] && !visited[currenti+1][currentj]) {
visited[currenti+1][currentj] = true;
Node tempNode = new Node(currenti+1, currentj);
queue.add(tempNode);
}
if(currentj+1 < islands[0].length && islands[currenti][currentj+1] && !visited[currenti][currentj+1]) {
visited[currenti][currentj+1]=true;
Node tempNode = new Node(currenti, currentj+1);
queue.add(tempNode);
}
if(currentj+1 < islands[0].length && currenti+1 < islands.length && islands[currenti+1][currentj+1] && !visited[currenti+1][currentj+1]) {
visited[currenti+1][currentj+1]=true;
Node tempNode = new Node(currenti, currentj+1);
queue.add(tempNode);
}
}
}

public static void main(String[] argc) {
IsLands islandsObj = new IsLands();
boolean[][] islands = {{true,false,false,false,true,true},{false,false,true,false,true,false},{false,false,true,false,false,false}};
int count = islandsObj.findNumberOfIslands(islands);
System.out.println(count);
}``````

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

``````class Node {
int iIndex;
int jIndex;
public Node(int iIndex, int jIndex) {
super();
this.iIndex = iIndex;
this.jIndex = jIndex;
}
public int getiIndex() {
return iIndex;
}
public void setiIndex(int iIndex) {
this.iIndex = iIndex;
}
public int getjIndex() {
return jIndex;
}
public void setjIndex(int jIndex) {
this.jIndex = jIndex;
}
public Node() {
super();
}
}
public int findNumberOfIslands(boolean[][] islands) {
boolean[][] visited= new boolean[islands.length][islands[0].length];
for(boolean row[]:visited)
Arrays.fill(row, false);
int count = 0;
for(int i=0; i < islands.length;i++) {
for(int j=0; j < islands[0].length;j++) {
if(islands[i][j] && !visited[i][j]) {
visitAdjacentPlaces(islands, visited, i, j);
count++;
}
}
}
return count;
}

public void visitAdjacentPlaces(boolean[][] islands, boolean[][] visited, int i, int j) {
Queue<Node> queue = new LinkedList<Node>();
visited[i][j] = true;
queue.add(new Node(i,j));
while(!queue.isEmpty()) {
Node node = queue.poll();
int currenti = node.getiIndex();
int currentj = node.getjIndex();
if(currenti+1 < islands.length && islands[currenti+1][currentj] && !visited[currenti+1][currentj]) {
visited[currenti+1][currentj] = true;
Node tempNode = new Node(currenti+1, currentj);
queue.add(tempNode);
}
if(currentj+1 < islands[0].length && islands[currenti][currentj+1] && !visited[currenti][currentj+1]) {
visited[currenti][currentj+1]=true;
Node tempNode = new Node(currenti, currentj+1);
queue.add(tempNode);
}
if(currentj+1 < islands[0].length && currenti+1 < islands.length && islands[currenti+1][currentj+1] && !visited[currenti+1][currentj+1]) {
visited[currenti+1][currentj+1]=true;
Node tempNode = new Node(currenti, currentj+1);
queue.add(tempNode);
}
}
}

public static void main(String[] argc) {
IsLands islandsObj = new IsLands();
boolean[][] islands = {{true,false,false,false,true,true},{false,false,true,false,true,false},{false,false,true,false,false,false}};
int count = islandsObj.findNumberOfIslands(islands);
System.out.println(count);
}``````

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

the "Islands Count problem",
duplicate from here: question?id=5708658983829504

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

I think the core to this problem is to be able to split it up into two functions.

The core to the problem is essentially this:

for each element in your matrix, if its land, check if its been visited already. If it has, continue, otherwise you have to explore it using whatever algorithm you want (they should all have equal performance since you have to visit all the nodes anyways).

Primary loop

``````def find_islands(aMatrix):
visited = []
islands = 0
for row in range(len(aMatrix)):
currow = aMatrix[row]
for col in (range(len(currow))):
if (aMatrix[row][col] == 'x' and not [row, col] in visited):
islands += 1
dfs(aMatrix, row, col, visited)
return islands``````

Depth First Search implementation to mark what's been visited.

``````def dfs(aMatrix, row, col, visited):
fringe = []
fringe.append((row, col))
while (fringe):
visiting = fringe.pop()
visited.append(visiting)
curcol = visiting[1]
currow = visiting[0]
successors = []
if (curcol + 1 < len(aMatrix)):
successors.append((currow, curcol+1))
if (currow + 1 < len(aMatrix[curcol])):
successors.append((currow+1, curcol))
if (curcol - 1 >= 0):
successors.append((currow, curcol-1))
if (currow - 1 >= 0):
successors.append((currow-1, curcol))
for successor in successors:
if successor not in visited and successor not in fringe and aMatrix[successor[0]][successor[1]] == 'x':
fringe.append(successor)``````

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

##################
# 0 1 2 3 4
#0 [[x,0,0,0,0],
#1 [0,0,x,x,0],
#2 [x,0,x,0,0],
#3 [x,0,0,0,x]]
##################
#In above case there are 4 islands -
# x then x then x,x then x
# x x

islands = [[1,0,0,0,0], [0,0,1,1,0], [1,0,1,0,0], [1,0,0,0,1]]

def findIslands():
numOfIslands = 0

for i in range(len(islands)):
for j in range(len(islands[i])):
if islands[i][j] == 1:
if i == 0 and j == 0:
numOfIslands += 1

if (islands[i-1][j] != 1) and (islands[i][j-1] != 1) and (islands[i-1][j-1] != 1):
numOfIslands += 1

print "Total number of islands = ", numOfIslands

def main():
findIslands()

if __name__ == '__main__':
main()

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

``````##################
#    0 1 2 3 4
#0 [[x,0,0,0,0],
#1  [0,0,x,x,0],
#2  [x,0,x,0,0],
#3  [x,0,0,0,x]]
##################
#In above case there are 4 islands -
# x then x then x,x then x
#        x      x

islands =  [[1,0,0,0,0], [0,0,1,1,0], [1,0,1,0,0], [1,0,0,0,1]]

def findIslands():
numOfIslands = 0

for i in range(len(islands)):
for j in range(len(islands[i])):
if islands[i][j] == 1:
if i == 0 and j == 0:
numOfIslands += 1

if (islands[i-1][j] != 1) and (islands[i][j-1] != 1) and (islands[i-1][j-1] != 1):
numOfIslands += 1

print "Total number of islands = ", numOfIslands

def main():
findIslands()

if __name__ == '__main__':
main()``````

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

##################
# 0 1 2 3 4
#0 [[x,0,0,0,0],
#1 [0,0,x,x,0],
#2 [x,0,x,0,0],
#3 [x,0,0,0,x]]
##################
#In above case there are 4 islands -
# x then x then x,x then x
# x x

``islands =  [[1,0,0,0,0], [0,0,1,1,0], [1,0,1,0,0], [1,0,0,0,1]]``

``def findIslands():``

``numOfIslands = 0``

``for i in range(len(islands)):``

``for j in range(len(islands[i])):``

``if islands[i][j] == 1:``

``if i == 0 and j == 0:``

``numOfIslands += 1``

``if (islands[i-1][j] != 1) and (islands[i][j-1] != 1) and (islands[i-1][j-1] != 1):``

``numOfIslands += 1``

``print "Total number of islands = ", numOfIslands``

``def main():``

``findIslands()``

``if __name__ == '__main__':``

``main()``

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

``````##################
#    0 1 2 3 4
#0 [[x,0,0,0,0],
#1  [0,0,x,x,0],
#2  [x,0,x,0,0],
#3  [x,0,0,0,x]]
##################
#In above case there are 4 islands -
# x then x then x,x then x
#        x      x

islands =  [[1,0,0,0,0], [0,0,1,1,0], [1,0,1,0,0], [1,0,0,0,1]]

def findIslands():
numOfIslands = 0

for i in range(len(islands)):
for j in range(len(islands[i])):
if islands[i][j] == 1:
if i == 0 and j == 0:
numOfIslands += 1

if (islands[i-1][j] != 1) and (islands[i][j-1] != 1) and (islands[i-1][j-1] != 1):
numOfIslands += 1

print "Total number of islands = ", numOfIslands

def main():
findIslands()

if __name__ == '__main__':
main()``````

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

let NL[i,j] be the number of lands in the matrix A[i,j], then:
NL[i, j] = NL[i-1, j] + NL[i, j-1] - NL[i-1, j-1], if NL[i, j] is water.
NL[i, j] = NL[i-1, j] + NL[i, j-1] - NL[i-1, j-1], if NL[i, j] is land either NL[i-1,j] or NL[i, j-1] is land.
NL[i,j] = NL[i-1, j] + NL[i, j-1] - NL[i-1, j-1] - 1, if NL[i,j], NL[i-1,j] and NL[i,j-1] are land.
NL[i,j] = NL[i-1, j] + NL[i, j-1] - NL[i-1, j-1] +1, if NL[i,j] is land and NL[i-1,j] and NL[i, j-1] are not land.

The time complexity is the size of the matrix.

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

using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace IsLandCount
{
class Program
{
static void Main(string[] args)
{
ArrayList islandCount = new ArrayList();
Console.WriteLine("Enter length and breadth of the world");
int size = int.Parse(Console.ReadLine());
Console.WriteLine("design islands");

for (int i=0; i< size;i++)
{
islandCount.Add(Console.ReadLine());

}

int count = 0;

foreach(string s in islandCount)
{
foreach(char c in s)
{
if(c == 'x' || c == 'X')
{
count++;
}
}
}

Console.WriteLine("Island Count : {0}", count);
Console.ReadLine();
}
}
}

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

``````using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace IsLandCount
{
class Program
{
static void Main(string[] args)
{
ArrayList islandCount = new ArrayList();
Console.WriteLine("Enter length and breadth of the world");
int size = int.Parse(Console.ReadLine());
Console.WriteLine("design islands");

for (int i=0; i< size;i++)
{
islandCount.Add(Console.ReadLine());

}

int count = 0;

foreach(string s in islandCount)
{
foreach(char c in s)
{
if(c == 'x' || c == 'X')
{
count++;
}
}
}

Console.WriteLine("Island Count : {0}", count);
Console.ReadLine();
}
}
}``````

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

For each cell check each adjacent cell only if it falls behind this cell or above this cell (i.e. only back check). If none of them are X - increment islands.

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

For each cell that has 1, check each adjacent cell only if it falls behind this cell or above this cell (i.e. only back check). If none of them are 1 - increment islands.

``````public int find(int[][] arr, int rows, int cols) {
int numOfIslands = 0;
for(int i = 0; i < rows; i++) {
for(int j = 0; j < rows; j++) {
if(
arr[i][j] == 1 &&
(j-1 < 0 || arr[i][j-1] != 1) &&
(i-1 < 0 || j-1 < 0 || arr[i-1][j-1] != 1) &&
(i-1 < 0 || arr[i-1][j]!=1) &&
(i-1 < 0 || j+1 >= cols || arr[i-1][j+1]!=1)
) {
++numOfIslands;
}
}
}
return numOfIslands;
}``````

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

``````Ex: Input
int arr[6][6]={
{1,1,0,0,0,1},
{0,1,0,0,0,1},
{0,0,1,1,0,0},
{0,0,0,0,0,0},
{0,0,1,1,0,0},
{0,0,0,0,1,0}
};

int find_ilands(const int arr[MAX_ROWS][MAX_COLS], const int rows, const int columns)
{
int i=0;
int j=0;
int islands = 0;
bool new_island = false;
for(i=0 ; i < rows; i++){
for(j=0; j<columns; j++){
new_island = true;
if(arr[i][j] == 1){
/*check if it is new island*/
if((i > 0) &&(j > 0)){
if((arr[i-1][j] == 1) || (arr[i][j-1] == 1) || (arr[i-1][j-1] == 1)){
new_island = false;
}
}else if(i == 0 && j > 0){
if(arr[i][j-1] == 1){
new_island = false;
}
}else if(j == 0 && i > 0){
if(arr[i-1][j] == 1){
new_island = false;
}
}
if(new_island){
islands++;
}
}
}
}
return islands;
}``````

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

``````int arr[6][6]={
{1,1,0,0,0,1},
{0,1,0,0,0,1},
{0,0,1,1,0,0},
{0,0,0,0,0,0},
{0,0,1,1,0,0},
{0,0,0,0,1,0}
};

int find_ilands(const int arr[][6], const int rows, const int columns)
{
int i=0;
int j=0;
int islands = 0;
bool new_island = false;
for(i=0 ; i < rows; i++){
for(j=0; j<columns; j++){
new_island = true;
if(arr[i][j] == 1){
printf("Found land at [%d] [%d]\n", i, j);
/*check if it is new island*/
if((i > 0) &&(j > 0)){
if((arr[i-1][j] == 1) || (arr[i][j-1] == 1) || (arr[i-1][j-1] == 1)){
new_island = false;
}
}else if(i == 0 && j > 0){
if(arr[i][j-1] == 1){
new_island = false;
}
}else if(j == 0 && i > 0){
if(arr[i-1][j] == 1){
new_island = false;
}
}
if(new_island){
islands++;
}
}
}
}
return islands;
}``````

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

Create a Point Class to with instance variable X and Y to store the location Matrix index .

public int findNumberOfIsland(int[][] arr){
boolean[][] visited = new boolean[arr.length][arr[0].length];
Stack<Point> stack = new Stack<>();
int noOfIsland =0;

for(int i =0 ; i < arr.length ; i++){
for(int j =0; j<arr[0].length; j++ ){
if(arr[i][j]== 1 && visited[i][j]== false){
Point p = new Point(i,j);
stack.push(p);
while(!stack.isEmpty()){
Point curr = stack.pop();
visited[curr.getX()][curr.getY()] = true;

//For checking Downward Movement
if(curr.getX()+1 < arr.length && arr[curr.getX()+1][curr.getY()] == 1 && visited[curr.getX()+1][curr.getY()] == false){
visited[curr.getX()+1][curr.getY()] = true;
Point temp = new Point(curr.getX()+1,curr.getY());
stack.push(temp);
}
//For checking Upward Movement
if(curr.getX()-1 > 0 && arr[curr.getX()-1][curr.getY()] == 1 && visited[curr.getX()-1][curr.getY()] == false ){
visited[curr.getX()-1][curr.getY()] = true;
Point temp = new Point(curr.getX()-1,curr.getY());
stack.push(temp);
}
//For checking Left Movement
if(curr.getY()-1 > 0 && arr[curr.getX()][curr.getY()-1] == 1 && visited[curr.getX()][curr.getY()-1] == false){
visited[curr.getX()][curr.getY()-1] = true;
Point temp = new Point(curr.getX(),curr.getY()-1);
stack.push(temp);
}
//For checking Right Movement
if(curr.getY()+1 < arr[0].length && arr[curr.getX()][curr.getY()+ 1] == 1 && visited[curr.getX()][curr.getY()+ 1] == false){
visited[curr.getX()][curr.getY()+ 1] = true;
Point temp = new Point(curr.getX(),curr.getY()+ 1);
stack.push(temp);
}
//For checking Upward Left Diagonal Movement
if(curr.getX()-1 > 0 && curr.getY()-1 > 0 && arr[curr.getX()-1][curr.getY()-1] == 1 && visited[curr.getX()-1][curr.getY()-1] == false){
visited[curr.getX()-1][curr.getY()-1] = true;
Point temp = new Point(curr.getX()-1,curr.getY()-1);
stack.push(temp);
}
//For checking Upward Right Diagonal Movement
if(curr.getX()-1 > 0 && curr.getY() +1 < arr[0].length && arr[curr.getX()-1][curr.getY()+1] == 1 && visited[curr.getX()-1][curr.getY()+1] == false){
visited[curr.getX()-1][curr.getY()+ 1] = true;
Point temp = new Point(curr.getX()-1,curr.getY()+ 1);
stack.push(temp);
}
//For checking Downward Left Diagonal Movement
if(curr.getX()+1 < arr.length && curr.getY()-1 > 0 && arr[curr.getX()+1][curr.getY()-1] == 1 && visited[curr.getX()+1][curr.getY()-1] == false){
visited[curr.getX()+1][curr.getY()-1] = true;
Point temp = new Point(curr.getX()-1,curr.getY()-1);
stack.push(temp);
}
//For checking Downward Right Diagonal Movement
if(curr.getX()+1 < arr.length && curr.getY() +1 < arr[0].length && arr[curr.getX()+1][curr.getY()+1] == 1 && visited[curr.getX()+1][curr.getY()+1] == false){
visited[curr.getX()+1][curr.getY()+1] = true;
Point temp = new Point(curr.getX()+1,curr.getY()+1);
stack.push(temp);
}
}
noOfIsland++;
}
}
}

return noOfIsland;
}

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

public int findNumberOfIsland(int[][] arr){
boolean[][] visited = new boolean[arr.length][arr[0].length];
Stack<Point> stack = new Stack<>();
int noOfIsland =0;

for(int i =0 ; i < arr.length ; i++){
for(int j =0; j<arr[0].length; j++ ){
if(arr[i][j]== 1 && visited[i][j]== false){
Point p = new Point(i,j);
stack.push(p);
while(!stack.isEmpty()){
Point curr = stack.pop();
visited[curr.getX()][curr.getY()] = true;

//For checking Downward Movement
if(curr.getX()+1 < arr.length && arr[curr.getX()+1][curr.getY()] == 1 && visited[curr.getX()+1][curr.getY()] == false){
visited[curr.getX()+1][curr.getY()] = true;
Point temp = new Point(curr.getX()+1,curr.getY());
stack.push(temp);
}
//For checking Upward Movement
if(curr.getX()-1 > 0 && arr[curr.getX()-1][curr.getY()] == 1 && visited[curr.getX()-1][curr.getY()] == false ){
visited[curr.getX()-1][curr.getY()] = true;
Point temp = new Point(curr.getX()-1,curr.getY());
stack.push(temp);
}
//For checking Left Movement
if(curr.getY()-1 > 0 && arr[curr.getX()][curr.getY()-1] == 1 && visited[curr.getX()][curr.getY()-1] == false){
visited[curr.getX()][curr.getY()-1] = true;
Point temp = new Point(curr.getX(),curr.getY()-1);
stack.push(temp);
}
//For checking Right Movement
if(curr.getY()+1 < arr[0].length && arr[curr.getX()][curr.getY()+ 1] == 1 && visited[curr.getX()][curr.getY()+ 1] == false){
visited[curr.getX()][curr.getY()+ 1] = true;
Point temp = new Point(curr.getX(),curr.getY()+ 1);
stack.push(temp);
}
//For checking Upward Left Diagonal Movement
if(curr.getX()-1 > 0 && curr.getY()-1 > 0 && arr[curr.getX()-1][curr.getY()-1] == 1 && visited[curr.getX()-1][curr.getY()-1] == false){
visited[curr.getX()-1][curr.getY()-1] = true;
Point temp = new Point(curr.getX()-1,curr.getY()-1);
stack.push(temp);
}
//For checking Upward Right Diagonal Movement
if(curr.getX()-1 > 0 && curr.getY() +1 < arr[0].length && arr[curr.getX()-1][curr.getY()+1] == 1 && visited[curr.getX()-1][curr.getY()+1] == false){
visited[curr.getX()-1][curr.getY()+ 1] = true;
Point temp = new Point(curr.getX()-1,curr.getY()+ 1);
stack.push(temp);
}
//For checking Downward Left Diagonal Movement
if(curr.getX()+1 < arr.length && curr.getY()-1 > 0 && arr[curr.getX()+1][curr.getY()-1] == 1 && visited[curr.getX()+1][curr.getY()-1] == false){
visited[curr.getX()+1][curr.getY()-1] = true;
Point temp = new Point(curr.getX()-1,curr.getY()-1);
stack.push(temp);
}
//For checking Downward Right Diagonal Movement
if(curr.getX()+1 < arr.length && curr.getY() +1 < arr[0].length && arr[curr.getX()+1][curr.getY()+1] == 1 && visited[curr.getX()+1][curr.getY()+1] == false){
visited[curr.getX()+1][curr.getY()+1] = true;
Point temp = new Point(curr.getX()+1,curr.getY()+1);
stack.push(temp);
}
}
noOfIsland++;
}
}
}

return noOfIsland;
}

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

``````// JavaScript

var matrix = [
[1, 0, 1, 0, 0],
[1, 0, 1, 1, 0],
[1, 0, 1, 0, 0],
[1, 1, 1, 0, 0],
[0, 0, 0, 0, 1]
];

var islandCount = function (matrix) {
var islands = [];

for (var row = 0; row < matrix.length; row++) {
for (var col = 0; col < matrix.length; col++) {

var nodeA = {
row: row,
col: col
};

if (matrix[row][col]) {
var indexesOfExistingIslands = [];

var existingIslandsWithNeighbors = _.filter(islands, function (island, idx) {
var islandHasNeighbors = _.some(island, function (nodeB) {
var sameCol = nodeB.col === nodeA.col;
var sameRow = nodeB.row === nodeA.row;
var rowIsOneAheadOrOneBehind = nodeB.row === (nodeA.row + 1) || nodeB.row === (nodeA.row - 1);
var colIsOneAheadOrOneBehind = nodeB.col === (nodeA.col + 1) || (nodeB.col === nodeA.col - 1);
return (sameCol && rowIsOneAheadOrOneBehind) || (sameRow && colIsOneAheadOrOneBehind);
});

if (islandHasNeighbors) {
indexesOfExistingIslands.push(idx);
}

return islandHasNeighbors;
});

if (existingIslandsWithNeighbors.length) {
if (existingIslandsWithNeighbors.length > 1) {
// create new island - a merger of all islands with neighboring nodes
var newlyMergedIsland = _.reduce(existingIslandsWithNeighbors, function (memoArr, island) {
return memoArr.concat(island);
}, []);
// filter out old islands
islands = _.filter(islands, function (island, idx) {
return !_.contains(indexesOfExistingIslands, idx);
});
islands.push(newlyMergedIsland)
} else {
// push node into single island with neighboring nodes
existingIslandsWithNeighbors[0].push(nodeA);
}
} else {
// no islands with neighboring nodes - create new island
var newIsland = [nodeA];
islands.push(newIsland);
}
}
}
}

return islands.length;
};``````

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

``````// JavaScript

var matrix = [
[1, 0, 1, 0, 0],
[1, 0, 1, 1, 0],
[1, 0, 1, 0, 0],
[1, 1, 1, 0, 0],
[0, 0, 0, 0, 1]
];

var islandCount = function (matrix) {
var islands = [];

for (var row = 0; row < matrix.length; row++) {
for (var col = 0; col < matrix.length; col++) {

var nodeA = {
row: row,
col: col
};

if (matrix[row][col]) {
var indexesOfExistingIslands = [];

var existingIslandsWithNeighbors = _.filter(islands, function (island, idx) {
var islandHasNeighbors = _.some(island, function (nodeB) {
var sameCol = nodeB.col === nodeA.col;
var sameRow = nodeB.row === nodeA.row;
var rowIsOneAheadOrOneBehind = nodeB.row === (nodeA.row + 1) || nodeB.row === (nodeA.row - 1);
var colIsOneAheadOrOneBehind = nodeB.col === (nodeA.col + 1) || (nodeB.col === nodeA.col - 1);
return (sameCol && rowIsOneAheadOrOneBehind) || (sameRow && colIsOneAheadOrOneBehind);
});

if (islandHasNeighbors) {
indexesOfExistingIslands.push(idx);
}

return islandHasNeighbors;
});

if (existingIslandsWithNeighbors.length) {
if (existingIslandsWithNeighbors.length > 1) {
// create new island - a merger of all islands with neighboring nodes
var newlyMergedIsland = _.reduce(existingIslandsWithNeighbors, function (memoArr, island) {
return memoArr.concat(island);
}, []);
// filter out old islands
islands = _.filter(islands, function (island, idx) {
return !_.contains(indexesOfExistingIslands, idx);
});
islands.push(newlyMergedIsland)
} else {
// push node into single island with neighboring nodes
existingIslandsWithNeighbors[0].push(nodeA);
}
} else {
// no islands with neighboring nodes - create new island
var newIsland = [nodeA];
islands.push(newIsland);
}
}
}
}

return islands.length;
};``````

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

``````// JavaScript

var matrix = [
[1, 0, 1, 0, 0],
[1, 0, 1, 1, 0],
[1, 0, 1, 0, 0],
[1, 1, 1, 0, 0],
[0, 0, 0, 0, 1]
];

var islandCount = function (matrix) {
var islands = [];

for (var row = 0; row < matrix.length; row++) {
for (var col = 0; col < matrix.length; col++) {

var nodeA = {
row: row,
col: col
};

if (matrix[row][col]) {
var indexesOfExistingIslands = [];

var existingIslandsWithNeighbors = _.filter(islands, function (island, idx) {
var islandHasNeighbors = _.some(island, function (nodeB) {
var sameCol = nodeB.col === nodeA.col;
var sameRow = nodeB.row === nodeA.row;
var rowIsOneAheadOrOneBehind = nodeB.row === (nodeA.row + 1) || nodeB.row === (nodeA.row - 1);
var colIsOneAheadOrOneBehind = nodeB.col === (nodeA.col + 1) || (nodeB.col === nodeA.col - 1);
return (sameCol && rowIsOneAheadOrOneBehind) || (sameRow && colIsOneAheadOrOneBehind);
});

if (islandHasNeighbors) {
indexesOfExistingIslands.push(idx);
}

return islandHasNeighbors;
});

if (existingIslandsWithNeighbors.length) {
if (existingIslandsWithNeighbors.length > 1) {
// create new island - a merger of all islands with neighboring nodes
var newlyMergedIsland = _.reduce(existingIslandsWithNeighbors, function (memoArr, island) {
return memoArr.concat(island);
}, []);
// filter out old islands
islands = _.filter(islands, function (island, idx) {
return !_.contains(indexesOfExistingIslands, idx);
});
islands.push(newlyMergedIsland)
} else {
// push node into single island with neighboring nodes
existingIslandsWithNeighbors[0].push(nodeA);
}
} else {
// no islands with neighboring nodes - create new island
var newIsland = [nodeA];
islands.push(newIsland);
}
}
}
}

return islands.length;
};``````

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

O(n^2) - char matrix represents the map, count only the bottom right X's of the islands, that is, skip the X's that have right neighbours or if one of the previous neighbouring X's in the row had a bottom neighbour skip all the X's of that island in the row, else islands++.

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

Connected Components algorithm in a graph

``````public class Solution {

public static class Point {
int row;
int col;
public Point(int row, int col) {
this.row = row;
this.col = col;
}

public boolean isValid(char[][] grid) {
int rows = grid.length;
int columns = grid[0].length;

return row >= 0 && row < rows && col >= 0 && col < columns && grid[row][col] == '1';
}

}
public static Point[] directions = {new Point(1,0),new Point(-1,0),new Point(0,1),new Point(0,-1)};

public int numIslands(char[][] grid) {

int rows = grid.length;
if(rows == 0){
return 0;
}
int columns = grid[0].length;

int component = 0;

boolean[][] visited = new boolean[rows][columns];

for (int i = 0; i< rows; i++) {
for (int j = 0; j< columns; j++) {
if (grid[i][j] == '1' && !visited[i][j]) {
visited[i][j] = true;
dfs(new Point(i,j), grid, visited);
component ++;
}

}
}

return component;
}

void dfs(Point start, char[][] grid, boolean[][] visited){
int rows = grid.length;
int columns = grid[0].length;

for(Point dir : directions) {
Point newPoint = new Point(start.row + dir.row, start.col + dir.col);
if(newPoint.isValid(grid) && !visited[newPoint.row][newPoint.col]) {
visited[newPoint.row][newPoint.col] = true;
dfs(newPoint, grid, visited);
}
}
}
}``````

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

this is the way I approach

``````typedef struct _co_ordinates{
int x;
int y;
} co_ordinates;
bool isValid(co_ordinates c, int size){
return (c.x >= 0 && c.x < size && c.y >= 0 && c.y < size) ? true : false;
}
co_ordinates left(co_ordinates c){
return { c.x - 1, c.y };
}
co_ordinates right(co_ordinates c){
return{ c.x + 1, c.y };
}
co_ordinates up(co_ordinates c){
return{ c.x, c.y - 1};
}
co_ordinates down(co_ordinates c){
return{ c.x, c.y + 1};
}
co_ordinates(*direction[4])(co_ordinates) = { up, right, down, left };

int countIsland(int** arr, int size){
int sum = 0;
for (int i = 0; i < size; i++){
for (int j = 0; j < size; j++){
if (arr[i][j] > 1) continue;
if (arr[i][j] == 0){
arr[i][j] = 2;
continue;
}
if (arr[i][j] == 1){
arr[i][j] = 3;
sum += countIslandUntil(arr, i, j, size);
}
}
}
return sum;
}
int countIslandUntil(int **arr, int x, int y, int size){
queue<co_ordinates> q;
co_ordinates c = { x, y };
q.push(c);
while (!q.empty()){
co_ordinates c = q.front();
q.pop();
int i = 4;
while (i){
co_ordinates temp = direction[--i](c);
if (isValid(temp,size) && arr[temp.x][temp.y] == 1){
arr[temp.x][temp.y] = 3;
q.push(temp);
}
}
}
return 1;
}``````

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

Please look what is the definition of island.

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

Simple dfs sol

``````public static int noOfIslands(int[][] matrix){
int count = 0;
int rows = matrix.length;
int cols = matrix[0].length;
for(int i = 0; i < rows; i++){
for(int j = 0; j < cols; j++){
if(matrix[i][j] == 1){
++count;
setZero(matrix, i, j, rows, cols);
}
}
}
return count;
}
public static void setZero(int[][] m, int i, int j, int rows, int cols){
if(i < 0 || j < 0 || i >= rows || j >= cols)
return;
if(m[i][j] == 0)
return;

m[i][j] = 0;
setZero(m, i-1, j, rows, cols);
setZero(m, i+1, j, rows, cols);
setZero(m, i, j-1, rows, cols);
setZero(m, i, j+1, rows, cols);
}``````

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