Facebook Interview Question SDE1s
Country: United States
I assume that islands are solid. I.e. an island can't have a lake in the middle.
The idea is to walk along the shore.
#include<iostream>
#include<vector>
#include<stack>
using namespace std;
bool Shore(vector<vector<int>> const &m, int r, int c)
{
if (r >= 0 &&
r < m.size() &&
c >= 0 &&
c < m[r].size() &&
m[r][c] == 1)
{
if (r + 1 >= m.size() ||
r - 1 < 0 ||
c + 1 >= m[r].size() ||
c - 1 < 0 ||
m[r + 1][c] == 0 ||
m[r - 1][c] == 0 ||
m[r][c + 1] == 0 ||
m[r][c - 1] == 0)
{
return true;
}
}
return false;
}
int PerimeterFromCell(vector<vector<int>> &m, int r, int c)
{
int perimeter = 0;
stack<pair<int, int>> st;
st.push(pair<int, int>(r, c));
while (!st.empty()) {
r = st.top().first;
c = st.top().second;
st.pop();
if (Shore(m, r, c)) {
++perimeter;
st.push(pair<int, int>(r + 1, c));
st.push(pair<int, int>(r - 1, c));
st.push(pair<int, int>(r, c + 1));
st.push(pair<int, int>(r, c - 1));
m[r][c] = 2;
}
}
return perimeter;
}
vector<int> Perimeters(vector<vector<int>> &m)
{
vector<int> out;
for (int r = 0; r < m.size(); ++r) {
for (int c = 0; c < m[r].size(); ++c) {
int perimeter = PerimeterFromCell(m, r, c);
if (perimeter > 0) {
out.push_back(perimeter);
}
}
}
return out;
}
int main()
{
vector<vector<int>> m = {
{0,0,0,0,1,1,1,1},
{0,1,1,1,0,0,1,1},
{0,1,1,1,0,0,1,1},
{0,1,1,0,0,1,0,0},
{0,0,0,1,1,1,0,0},
{0,0,0,1,1,1,1,0},
{0,1,0,1,1,1,1,0}
};
vector<int> out = Perimeters(m);
for (int n : out) {
cout << n << ", ";
}
cout << "\n";
return 0;
}
If perimeter is the number of steps to walk around an island, you can just search for connected components and count, how many of those are pieces that border to the water.
This will detect islands and islands within islands and the perimiter for the case of islands with a lake just include the inner shore line.
An alternative, is to use a maze runner, it's more complicated tough. This way, it detects only the outer shore line and ignores the inner part of the island. That way it can get fast on large islands, but it will not detect islands within islands.
/*
000
010
000
perimeter = 1
0000
0110
0110
0000
perimeter = 4
00000
01110
01010
01010
01110
00000
perimter = 10
0000000
0*****0
00**1*0
000***0
0000000
* indicates perimeter (would be '1's)
perimeter = 11
0000000
0*****0
0000000
perimeter = 5
0000000
0*000*0
0*****0
0**0*00
perimeter = 10
*/
#include <vector>
#include <queue>
#include <array>
#include <iostream>
using namespace std;
const int DIRECTIONS = 4; // up,right,down,left
const array<array<int, 2>, DIRECTIONS> MOVES{ { { -1, 0 }, { 0, 1 }, { 1, 0 }, { 0, -1 } } };
const array<array<int, 2>, DIRECTIONS> LEFT_FIELD{ {{0, -1}, { -1, 0 }, {0, 1}, { 1, 0 } } };
ostream& operator <<(ostream& os, const vector<int>& v);
ostream& operator <<(ostream& os, const vector<vector<int>>& vv);
bool is_within_map(vector<vector<int>>& map, int x, int y);
bool is_unvisited_land(vector<vector<int>>& map, int x, int y);
bool is_water(vector<vector<int>>& map, int x, int y);
bool is_unvisited_water(vector<vector<int>>& map, int x, int y);
bool is_waterLeft(vector<vector<int>>& map, int x, int y, int d);
vector<int> calc_perimeter(vector<vector<int>>& map)
{
vector<int> result;
deque<pair<int, int>> s;
for (int x = 0; x < map.size(); ++x) s.push_front({ x, -1 });
while (!s.empty()) {
int x = s.back().first;
int y = s.back().second;
s.pop_back();
if (is_unvisited_land(map, x, y)) {
// start maze runner here
int perimeter = 0;
int d = 0, ox = -1, oy = -1, od = 0; // originates from
do {
if (is_unvisited_land(map, x, y)) { // if it hasn't been visited
map[x][y] = 3; // visited land
perimeter++; // count the field as perimeter
}
if (is_unvisited_water(map, x, y + 1)) { // keep scanning
s.push_front({ x, y + 1 });
}
// adjust direction to not walk into water
for (int i = 0; i < DIRECTIONS; ++i, d = (d + 1) % DIRECTIONS) {
if (!is_water(map, x + MOVES[d][0], y + MOVES[d][1])) break;
}
if (ox == -1 && oy == -1) { // is it the first step?
ox = x;
oy = y;
od = d;
} else {
if (x == ox && y == oy && d == od) break; // walked around once
}
x += MOVES[d][0];
y += MOVES[d][1];
if (!is_waterLeft(map, x, y, d)) { // no water on the left-> turn left
d = (d - 1 + DIRECTIONS) % DIRECTIONS;
}
} while (true);
result.push_back(perimeter);
} else if(is_water(map, x, y)) { // it's water
if (is_within_map(map, x, y)) {
map[x][y] = 2; // visited water
}
if (is_within_map(map, x, y + 1)) { // move further right
s.push_front({ x, y + 1 });
}
}
}
return result;
}
int main()
{
vector<vector<int>> map{
{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, },
{0, 1, 0, 0, 0, 1, 1, 1, 0, 0, 1, 1, 1, 1, 1, 0, 0, 1, },
{0, 0, 0, 1, 0, 1, 0, 1, 0, 0, 0, 1, 1, 1, 1, 0, 0, 1, },
{0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 1, 1, 0, 0, 1, },
{0, 1, 1, 0, 0, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, },
{0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, },
{0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 1, 1, 0, },
{0, 1, 1, 1, 1, 1, 0, 0, 1, 1, 1, 1, 1, 0, 0, 1, 0, 0, },
{0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 1, 0, 0, 0, 0, 0, 0, },
};
cout << "before:" << endl << map << endl << endl;
cout << "result:" << calc_perimeter(map) << endl;
cout << "after:" << endl << map << endl << endl;
}
/* output
before:
{
{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0}
{0,1,0,0,0,1,1,1,0,0,1,1,1,1,1,0,0,1}
{0,0,0,1,0,1,0,1,0,0,0,1,1,1,1,0,0,1}
{0,0,0,0,0,1,0,1,0,0,0,0,0,1,1,0,0,1}
{0,1,1,0,0,1,1,1,0,1,1,1,1,1,1,1,1,1}
{0,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0}
{0,0,0,0,0,0,0,0,1,0,0,0,1,0,0,1,1,0}
{0,1,1,1,1,1,0,0,1,1,1,1,1,0,0,1,0,0}
{0,0,0,0,0,0,0,0,1,1,0,1,0,0,0,0,0,0}
}
result:{1,4,5,1,10,10,23,3}
after:
{
{2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2}
{2,3,2,2,2,3,3,3,2,2,3,3,3,3,3,2,2,3}
{2,2,2,3,2,3,2,3,2,2,2,3,3,3,3,2,2,3}
{2,2,2,2,2,3,2,3,2,2,2,2,2,3,3,2,2,3}
{2,3,3,2,2,3,3,3,2,3,3,3,3,3,3,3,3,3}
{2,3,3,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2}
{2,2,2,2,2,2,2,2,3,2,2,2,3,2,2,3,3,2}
{2,3,3,3,3,3,2,2,3,3,3,3,3,2,2,3,2,2}
{2,2,2,2,2,2,2,2,3,3,2,3,2,2,2,2,2,2}
}
*/
bool is_within_map(vector<vector<int>>& map, int x, int y)
{
return (static_cast<unsigned int>(x) < map.size()
&& static_cast<unsigned int>(y) < map[x].size());
}
bool is_unvisited_land(vector<vector<int>>& map, int x, int y)
{
return is_within_map(map, x, y) && map[x][y] == 1;
}
bool is_water(vector<vector<int>>& map, int x, int y)
{
return !is_within_map(map, x, y) || map[x][y] == 0 || map[x][y] == 2; // visited or unvisited water
}
bool is_unvisited_water(vector<vector<int>>& map, int x, int y)
{
return is_within_map(map, x, y) && map[x][y] == 0;
}
bool is_waterLeft(vector<vector<int>>& map, int x, int y, int d)
{
return is_water(map, x + LEFT_FIELD[d][0], y + LEFT_FIELD[d][1]);
}
ostream& operator <<(ostream& os, const vector<int>& v)
{
os << "{";
bool first = true;
for (auto e : v) {
if (!first) os << "," << e;
else os << e;
first = false;
}
os << "}";
return os;
}
ostream& operator <<(ostream& os, const vector<vector<int>>& vv)
{
os << "{" << endl;
for (auto v : vv) {
os << " " << v << endl;
}
os << "}";
return os;
}
Python solution:
def islandParameter(matrix):
def dfs(matrix, i, j):
if i<0 or j<0 or i>=len(matrix) or j>=len(matrix[0]) or not matrix[i][j]:
return 1
if matrix[i][j]==-1:
return 0
matrix[i][j], ret = -1,0
corrd = [(i+1,j),(i-1,j),(i,j+1),(i,j-1)]
for corr in corrd:
ret += dfs(matrix, corr[0], corr[1])
return ret
res = 0
for i in range(len(matrix)):
for j in range(len(matrix[0])):
if matrix[i][j]:
res += dfs(matrix,i,j)
print('Islanda parameter : {}'.format(res))
def main():
#islandParameter
matrix = [[0,1,0,0],
[1,1,1,0],
[0,1,0,0],
[1,1,0,0]]
#islandParameter(matrix)
So if there are 5 islands in the grid, then we are supposed to return perimeter of all 5 islands?
- Panda November 07, 2017