unknown Interview Question xyzs
Country: United States
We need a group table and a group matrix. At initiial state, a group table is empty and a group matrix is filled 0.
groupID: {}
groupMatrix:
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
We visit each cell from top left corner and move left. Cell's left and up are 0 then cell get a new groupID.
groupID: { 1(1), 2(2) }
groupMatrix:
0 1 0 2 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
Now, we fill groupID to 3rd cell of 2nd row.
groupID: { 1(1), 2(2), 3(3) }
groupMatrix:
0 1 0 2 0
0 0 3 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
4th cell of 2nd row has 2 candidates of groupID, 3 from left cell and 2 from up cell. We choice lower gropuID. And bigger groupID change to lower groupID.
groupID: { 1(1), 2(2), 3(2) }
groupMatrix:
0 1 0 2 0
0 0 3 2 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
This is final state. Number of groups is number of items of same groupID index and value.
groupID: { 1(1), 2(2), 3(2), 4(4), 5(5), 6(6), 7(7) }
groupMatrix:
0 1 0 2 0
0 0 3 2 2
4 0 0 2 0
0 5 5 0 0
6 0 5 0 7
c++, implementation, O(n)
int countOfIslands(vector<vector<int>> matrix) {
vector<vector<int>> groupMatrix;
vector<int> groupID;
int nextGroup;
int i, x, y, left, up, cnt;
groupMatrix = matrix;
for (i = 0; i < groupMatrix.size(); i++) {
groupMatrix[i].assign(groupMatrix[i].size(), 0);
}
groupID.push_back(0);
nextGroup = 1;
for (y = 0; y < matrix.size(); y++) {
for (x = 0; x < matrix[y].size(); x++) {
if (matrix[y][x] == 0) continue;
left = 0;
if (x != 0) left = groupMatrix[y][x - 1];
left = groupID[left];
up = 0;
if (y != 0) up = groupMatrix[y - 1][x];
up = groupID[up];
if (left == 0 && up == 0) {
groupMatrix[y][x] = nextGroup;
groupID.push_back(nextGroup);
nextGroup++;
} else if (left != 0 && up != 0) {
if (left > up) {
groupMatrix[y][x] = up;
groupID[left] = up;
} else {
groupMatrix[y][x] = left;
groupID[up] = left;
}
} else if (up == 0) {
groupMatrix[y][x] = left;
} else {
groupMatrix[y][x] = up;
}
}
}
cnt = 0;
for (i = 1; i < groupID.size(); i++) {
if (i == groupID[i]) cnt++;
}
return cnt;
}
If we take input matrix with 24.000 islands, you algorithm is 2.5 times faster than the algorithm provided by ikoryf. Thanks! But the ikoryf's algorithm is a little more understandable, to my mind.
C++ Code For finding Connected Components.
#include <iostream>
void printMatrix(int** matrix, int numRows, int numCols)
{
for(int i=0; i < numRows; i++)
{
for(int j=0; j < numCols; j++)
{
std::cout << matrix[i][j] << "\t";
}
std::cout << std::endl;
}
}
void findCC(int** matrix, int numRows, int numCols, int row, int col, int Label)
{
if(matrix[row][col] == 1)
{
matrix[row][col] = Label;
}
else
{
return;
}
if(row+1 < numRows) findCC(matrix, numRows, numCols, row+1, col, Label);
if(row-1 >= 0) findCC(matrix, numRows, numCols, row-1, col, Label);
if(col+1 < numCols) findCC(matrix, numRows, numCols, row, col+1, Label);
if(col-1 >= 0) findCC(matrix, numRows, numCols, row, col-1, Label);
}
int main()
{
int numRows = 5, numCols = 5;
int data[5][5] = {{ 0, 1, 0, 1, 0},
{ 0, 0, 1, 1, 1},
{ 1, 0, 0, 1, 0},
{ 0, 1, 1, 0, 0},
{ 1, 0, 1, 0, 1}};
int** matrix;
matrix = new int*[numRows];
for(int i=0; i < numRows; i++)
{
matrix[i] = new int[numCols];
for(int j=0; j < numCols; j++)
{
matrix[i][j] = data[i][j];
}
}
printMatrix(matrix, numRows, numCols);
int numConnectedComp = 0;
for(int i=0; i < numRows; i++)
{
for(int j=0; j < numCols; j++)
{
if(matrix[i][j] == 1)
{
numConnectedComp++;
findCC(matrix, numRows, numCols, i, j, numConnectedComp+1);
}
}
}
std::cout << "No. of CC : " << numConnectedComp << std::endl;
printMatrix(matrix, numRows, numCols);
for(int i=0; i < numRows; i++)
{
delete[] matrix[i];
}
delete[] matrix;
}
For counting the number of islands, here is another solution.
0. initialize numIslands to 0
1. Scan the matrix in a linear fashion across rows and columns
2. At each cell (i, j), check the adjacent cells at (i, j-1) and (i-1, j).
if both are part of an island already, merge these. (numIslands--)
if only one of these is an island, join the same. (numIslands does not change)
if neither are an island, then create a new island (numIslands++)
3. report the final numIslands count
Time Complexity: O(M)
Space Complexity: O(1)
//c++ implementation without using an extra array and least complexity O(n^2)..
#include<iostream>
using namespace std;
int n=5;
int val(int (&arr)[5][5],int i,int j)
{
if(i<0||i>n-1||j<0||j>n-1)
return 0;
else if(arr[i][j]!=1)
return 0;
else if(arr[i][j]==1)
{
arr[i][j]=2;
return 1+val(arr,i+1,j)+val(arr,i+1,j+1)+val(arr,i+1,j-1)+val(arr,i,j+1)+val(arr,i-1,j+1)+val(arr,i-1,j-1)+val(arr,i,j-1)+val(arr,i-1,j);
}
}
int main()
{
int arr[5][5]={{1,1,0,0,0},
{0,1,1,0,0},
{0,0,1,0,1},
{1,0,0,0,1},
{0,1,0,1,1}};
int a,b,i,j,k;
int max=-1,count;
for(i=0;i<5;i++)
{for(j=0;j<5;j++)
{
if(arr[i][j]==1)
{
count =val(arr,i,j);
}
if(count>max)
{max=count;
}}
}
cout<<max;
}
//c++ implementation with no extra space complexity
#include<iostream>
using namespace std;
int n=5;
int val(int (&arr)[5][5],int i,int j)
{
if(i<0||i>n-1||j<0||j>n-1)
return 0;
else if(arr[i][j]!=1)
return 0;
else if(arr[i][j]==1)
{
arr[i][j]=2;
return 1+val(arr,i+1,j)+val(arr,i+1,j+1)+val(arr,i+1,j-1)+val(arr,i,j+1)+val(arr,i-1,j+1)+val(arr,i-1,j-1)+val(arr,i,j-1)+val(arr,i-1,j);
}
}
int main()
{
int arr[5][5]={{1,1,0,0,0},
{0,1,1,0,0},
{0,0,1,0,1},
{1,0,0,0,1},
{0,1,0,1,1}};
int a,b,i,j,k;
int max=-1,count;
for(i=0;i<5;i++)
{for(j=0;j<5;j++)
{
if(arr[i][j]==1)
{
count =val(arr,i,j);
}
if(count>max)
{max=count;
}}
}
cout<<max;
}
c ++ implementation without using extra space
#include<iostream>
using namespace std;
int n=5;
int val(int (&arr)[5][5],int i,int j)
{
if(i<0||i>n-1||j<0||j>n-1)
return 0;
else if(arr[i][j]!=1)
return 0;
else if(arr[i][j]==1)
{
arr[i][j]=2;
return 1+val(arr,i+1,j)+val(arr,i+1,j+1)+val(arr,i+1,j-1)+val(arr,i,j+1)+val(arr,i-1,j+1)+val(arr,i-1,j-1)+val(arr,i,j-1)+val(arr,i-1,j);
}
}
int main()
{
int arr[5][5]={{1,1,0,0,0},
{0,1,1,0,0},
{0,0,1,0,1},
{1,0,0,0,1},
{0,1,0,1,1}};
int a,b,i,j,k;
int max=-1,count;
for(i=0;i<5;i++)
{for(j=0;j<5;j++)
{
if(arr[i][j]==1)
{
count =val(arr,i,j);
}
if(count>max)
{max=count;
}}
}
cout<<max;
}
c++ implementation without using extra space
#include<iostream>
using namespace std;
int n=5;
int val(int (&arr)[5][5],int i,int j)
{
if(i<0||i>n-1||j<0||j>n-1)
return 0;
else if(arr[i][j]!=1)
return 0;
else if(arr[i][j]==1)
{
arr[i][j]=2;
return 1+val(arr,i+1,j)+val(arr,i+1,j+1)+val(arr,i+1,j-1)+val(arr,i,j+1)+val(arr,i-1,j+1)+val(arr,i-1,j-1)+val(arr,i,j-1)+val(arr,i-1,j);
}
}
int main()
{
int arr[5][5]={{1,1,0,0,0},
{0,1,1,0,0},
{0,0,1,0,1},
{1,0,0,0,1},
{0,1,0,1,1}};
int a,b,i,j,k;
int max=-1,count;
for(i=0;i<5;i++)
{for(j=0;j<5;j++)
{
if(arr[i][j]==1)
{
count =val(arr,i,j);
}
if(count>max)
{max=count;
}}
}
cout<<max;
}
c++ implementation without using extra space
#include<iostream>
using namespace std;
int n=5;
int val(int (&arr)[5][5],int i,int j)
{
if(i<0||i>n-1||j<0||j>n-1)
return 0;
else if(arr[i][j]!=1)
return 0;
else if(arr[i][j]==1)
{
arr[i][j]=2;
return 1+val(arr,i+1,j)+val(arr,i+1,j+1)+val(arr,i+1,j-1)+val(arr,i,j+1)+val(arr,i-1,j+1)+val(arr,i-1,j-1)+val(arr,i,j-1)+val(arr,i-1,j);
}
}
int main()
{
int arr[5][5]={{1,1,0,0,0},
{0,1,1,0,0},
{0,0,1,0,1},
{1,0,0,0,1},
{0,1,0,1,1}};
int a,b,i,j,k;
int max=-1,count;
for(i=0;i<5;i++)
{for(j=0;j<5;j++)
{
if(arr[i][j]==1)
{
count =val(arr,i,j);
}
if(count>max)
{max=count;
}}
}
cout<<max;
}
couldn't we just visit each cell in the matrix once, with a time complexity linear to the number of cells O(n*m), and check for adjacent land that is already visited?
algorithm:
initialize islands counter to 0
iterate through cells.
if cell is unvisited land,
then mark it as visited. (this could be done destructively, or if the cells contain booleans through a second mirrored data structure).
if cell is not adjacent to visited land (top, right, bottom, left are all sea, edge, or unvisited land),
then increment the island counter. (we may decrement it again if what appears to be multiple islands come together later on)
if cell is adjacent to more than 1 visited land, decrement islands by adjacentVisitedIslands -1.
return islands
couldn't we just do this by iterating through the cells in the matrix once, with a runtime linear to the amount of cells, by keeping track of the visited land? O(n*m)
algorithm:
initialize an island counter.
for each cell in the matrix,
if cell is unvisited land, then mark land as visited. (this can be done destructively, or if the backing data are booleans, then with a mirrored data structure.)
if cell is not adjacent to visited land, then increment the island counter (note: we may decrement the island counter later on if multiple islands end up joining together.)
if cell is adjacent to 2-4 visited lands, then decrement the island counter by the number of adjacent visited land(s) - 1.
after visiting each cell in the matrix, return the island counter
protected void Button29_Click(object sender, EventArgs e)
{
string seastring = "{1, 1, 0, 0, 0}, {0, 1, 0, 0, 1}, {1, 0, 0, 1, 1}, {0, 0, 0, 0, 0}, {1, 0, 1, 0, 1}"; //TextBox20.Text.ToLower();//input sea string
int shipsize = 3; // Convert.ToInt32(TextBox21.Text); // ship size
#region cal row and col cnt
int rowcnt = seastring.Count(q => q == '}');
int a = seastring.IndexOf('{');
int b = seastring.IndexOf('}');
int colcnt = 0;
for (int i = a; i < b; i++)
{
if (seastring[i] == ',')
{
colcnt++;
}
}
colcnt++;
#endregion
#region assign seastring to 2D arr
seastring = seastring.Replace("{", string.Empty).Replace("}", string.Empty).Replace(",", string.Empty).Replace(" ", string.Empty);
int[,] arr = new int[rowcnt, colcnt];
int k = 0;
for (int i = 0; i < rowcnt; i++)
{
for (int j = 0; j < colcnt; j++)
{
arr[i, j] = Convert.ToInt32("" + seastring[k] + "");
k++;
}
}
#endregion
#region seas check
Dictionary<int, int> seas = new Dictionary<int, int>();
int seaid = 0, sealength = 0;
bool toAdd = false;
for (int t = 0; t < rowcnt; t++)
{
for (int u = 0; u < colcnt; u++)
{
if (arr[t, u] == 1)
{
seaid++;
sealength++;
toAdd = true;
if (t < rowcnt-1)
{
if (arr[t + 1, u] == 1)
{
sealength++;
arr[t + 1, u] = 0;
}
}
if (t != 0)
{
if (arr[t - 1, u] == 1)
{
sealength++;
arr[t - 1, u] = 0;
}
}
if (u < colcnt - 1)
{
if (arr[t, u + 1] == 1)
{
sealength++;
arr[t, u + 1] = 0;
}
}
if (u != 0)
{
if (arr[t, u - 1] == 1)
{
sealength++;
arr[t, u - 1] = 0;
}
}
if(t!=0 && u != 0)
{
if (arr[t - 1, u - 1] == 1)
{
sealength++;
arr[t - 1, u - 1] = 0;
}
}
if (u != 0 && t < rowcnt - 1)
{
if (arr[t + 1, u - 1] == 1)
{
sealength++;
arr[t + 1, u - 1] = 0;
}
}
if((u < (colcnt - 1)) && (t < (rowcnt - 1)))
{
if (arr[t + 1, u + 1] == 1)
{
sealength++;
arr[t + 1, u + 1] = 0;
}
}
if (t != 0 && (u < (colcnt - 1)))
{
if (arr[t - 1, u + 1] == 1)
{
sealength++;
arr[t - 1, u + 1] = 0;
}
}
}
if (toAdd)
{
seas.Add(seaid, sealength);
sealength = 0;
toAdd = false;
}
}
}
#endregion
#region final output cal comparing shipsize and sea size
int oup = 0;
foreach (var seasize in seas.Values)
{
if (shipsize <= seasize)
{
oup++;
}
}
#endregion
}
protected void Button29_Click(object sender, EventArgs e)
{
string seastring = "{1, 1, 0, 0, 0}, {0, 1, 0, 0, 1}, {1, 0, 0, 1, 1}, {0, 0, 0, 0, 0}, {1, 0, 1, 0, 1}"; //TextBox20.Text.ToLower();//input sea string
int shipsize = 3; // Convert.ToInt32(TextBox21.Text); // ship size
#region cal row and col cnt
int rowcnt = seastring.Count(q => q == '}');
int a = seastring.IndexOf('{');
int b = seastring.IndexOf('}');
int colcnt = 0;
for (int i = a; i < b; i++)
{
if (seastring[i] == ',')
{
colcnt++;
}
}
colcnt++;
#endregion
#region assign seastring to 2D arr
seastring = seastring.Replace("{", string.Empty).Replace("}", string.Empty).Replace(",", string.Empty).Replace(" ", string.Empty);
int[,] arr = new int[rowcnt, colcnt];
int k = 0;
for (int i = 0; i < rowcnt; i++)
{
for (int j = 0; j < colcnt; j++)
{
arr[i, j] = Convert.ToInt32("" + seastring[k] + "");
k++;
}
}
#endregion
#region seas check
Dictionary<int, int> seas = new Dictionary<int, int>();
int seaid = 0, sealength = 0;
bool toAdd = false;
for (int t = 0; t < rowcnt; t++)
{
for (int u = 0; u < colcnt; u++)
{
if (arr[t, u] == 1)
{
seaid++;
sealength++;
toAdd = true;
if (t < rowcnt-1)
{
if (arr[t + 1, u] == 1)
{
sealength++;
arr[t + 1, u] = 0;
}
}
if (t != 0)
{
if (arr[t - 1, u] == 1)
{
sealength++;
arr[t - 1, u] = 0;
}
}
if (u < colcnt - 1)
{
if (arr[t, u + 1] == 1)
{
sealength++;
arr[t, u + 1] = 0;
}
}
if (u != 0)
{
if (arr[t, u - 1] == 1)
{
sealength++;
arr[t, u - 1] = 0;
}
}
if(t!=0 && u != 0)
{
if (arr[t - 1, u - 1] == 1)
{
sealength++;
arr[t - 1, u - 1] = 0;
}
}
if (u != 0 && t < rowcnt - 1)
{
if (arr[t + 1, u - 1] == 1)
{
sealength++;
arr[t + 1, u - 1] = 0;
}
}
if((u < (colcnt - 1)) && (t < (rowcnt - 1)))
{
if (arr[t + 1, u + 1] == 1)
{
sealength++;
arr[t + 1, u + 1] = 0;
}
}
if (t != 0 && (u < (colcnt - 1)))
{
if (arr[t - 1, u + 1] == 1)
{
sealength++;
arr[t - 1, u + 1] = 0;
}
}
}
if (toAdd)
{
seas.Add(seaid, sealength);
sealength = 0;
toAdd = false;
}
}
}
#endregion
#region final output cal comparing shipsize and sea size
int oup = 0;
foreach (var seasize in seas.Values)
{
if (shipsize <= seasize)
{
oup++;
}
}
#endregion
}
Java implementation using flood fill, O(n^2)
- ikoryf November 11, 2015public class IslandCount { public static void main(String[] args) { int[][] sea = new int[][] { new int[] {0, 1, 0, 1, 0}, new int[] {0, 0, 1, 1, 1}, new int[] {1, 0, 0, 1, 0}, new int[] {0, 1, 1, 0, 0}, new int[] {1, 0, 1, 0, 1} }; int numOfIslands = IslandCount.countIslands(sea); System.out.println("Number of islands is "+numOfIslands); } public static int countIslands(int[][] sea) { boolean[][] checked = new boolean[sea.length][sea.length]; for (int i = 0; i < sea.length; i++) { for (int j = 0; j < sea.length; j++) { checked[i][j] = false; } } return countIslands(sea, checked); } public static int countIslands(int[][] sea, boolean[][] checked) { int numOfIslands = 0; for (int i = 0; i < sea.length; i++) { for (int j = 0; j < sea.length; j++) { if (checked[i][j]) continue; if (sea[i][j] == 0) { checked[i][j] = true; continue; } numOfIslands++; floodFill(i, j, sea, checked); } } return numOfIslands; } public static void floodFill(int row, int col, int[][] sea, boolean[][] checked) { if (sea[row][col] == 0 || checked[row][col]) return; checked[row][col] = true; if (col < sea.length - 1) floodFill(row, col+1, sea, checked); if (row < sea.length - 1) floodFill(row+1, col, sea, checked); if (col > 0) floodFill(row, col-1, sea, checked); if (row > 0) floodFill(row-1, col, sea, checked); } }