This is a Facebook interview question for Android developer from careercup. Here is the original thread,
"
A museum was represented by a square matrix that was filled with O, G, and W where O represented open space G represented guards, and W represented walls. Write a function that accepts the square matrix and returns another square matrix where all of the O's in the matrix are replaced with the number of how many spaces they are away from a guard, without being able to go through any walls.
".
2. Data Structure and Algorithm
Mapping of the museum:
Given a museum there are 3 things to represent, open ground, guard and wall. The key here is to use wise data structure to represent museum in memory. In a common-sense scenario there are a few guards and plenty of open guards. Instead of a full size of grid to model museum two hash sets are to represent guards and walls.
- Location: row and column
- A hash set of locations to represent guards's position in museum
- A hash set of locations to represent wall's position in museum
- A hash map of locations as key and distance to guard as value to represent open group to guard
- Any open group not appearing in above hash map means isolated to guards
Algorithm:
Each guard has children nodes in the grid of possible directions to reach them (in the case of implementation in this post 4 directions - left, right, up and down). Therefore it is not hard to link to graph problem. Each node is linked to 4 neighbors (left, right , up and down). Each iteration expand one step from guards. Terminate expanding if reaches wall/guard/open-ground-already-visited and take the result (location + breadth-of-traverse) if reaches an open ground. In this case it is breath-first traverse the museum, which guarantees that the shortest path from open ground to its reachable guards.
3. C++ Implementation
// ********************************************************************************
// Implementation
// ********************************************************************************
#include <list>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <vector>
enum class MuseumItem
{
WALL = 0,
OPEN,
GUARD
};
struct LocHashFunc
{
size_t operator()(const std::tuple<size_t, size_t> &loc) const {
size_t row, col;
std::tie<size_t, size_t>(row, col) = loc;
return std::hash<size_t>()(row) ^ std::hash<size_t>()(col);
}
bool operator()(const std::tuple<size_t, size_t> &lhs,
const std::tuple<size_t, size_t> &rhs) const {
return lhs == rhs;
}
};
using LocationMap = std::unordered_set<std::tuple<size_t, size_t>, LocHashFunc, LocHashFunc>;
using LocAndDistMap = std::unordered_map<std::tuple<size_t, size_t>, int, LocHashFunc, LocHashFunc>;
bool ParserMuseumMap(const std::vector<std::vector<MuseumItem>> &museum,
LocationMap &guards,
LocationMap &walls)
{
// for this implementation, the mesum must be square
const size_t ROWS = museum.size();
if (ROWS == 0) {
return false;
}
const size_t COLS = museum[0].size();
auto itEnd = museum.end();
size_t row = 0, col = 0;
for (auto it = museum.begin(); it != itEnd; ++it, ++row) {
if (it->size() != COLS) {
return false; // enforce square map
}
auto itRowEnd = it->end();
col = 0;
for (auto itRow = it->begin(); itRow != itRowEnd; ++itRow, ++col) {
switch (*itRow) {
case MuseumItem::WALL:
walls.insert(std::make_tuple(row, col));
break;
case MuseumItem::OPEN:
break;
case MuseumItem::GUARD:
guards.insert(std::make_tuple(row, col));
break;
default:
return false;
}
}
}
return true;
}
void ExpandSeach(const std::tuple<size_t, size_t> &loc,
const LocationMap &guards,
const LocationMap &walls,
const size_t distance,
LocAndDistMap & distances,
std::list < std::tuple<size_t, size_t> > &toVisits)
{
if (walls.find(loc) != walls.end()) {
return;
}
if (guards.find(loc) != guards.end()) {
return;
}
if (distances.find(loc) == distances.end()) {
distances.insert(std::make_pair(loc, distance));
toVisits.push_back(loc);
}
}
const LocAndDistMap GetDistances(const size_t ROWS,
const size_t COLS,
const LocationMap &guards,
const LocationMap &walls)
{
LocAndDistMap distances;
std::list<std::tuple<size_t, size_t>> toVisits(guards.begin(), guards.end());
toVisits.push_back(std::tuple<size_t, size_t>{-1, -1});
LocationMap visited;
size_t dist = 1;
size_t row, col;
size_t distance = 1;
while (!toVisits.empty()) {
std::tie<size_t, size_t>(row, col) = toVisits.front();
if (row == -1 && col == -1) {
++distance;
toVisits.pop_front();
if (toVisits.empty()) {
break;
}
toVisits.push_back(std::make_tuple(-1, -1));
}
else {
if (row > 0) {
auto loc = std::make_tuple( row - 1, col );
ExpandSeach(loc, guards, walls, distance, distances, toVisits);
}
if (row != (ROWS - 1)) {
auto loc = std::make_tuple(row + 1, col);
ExpandSeach(loc, guards, walls, distance, distances, toVisits);
}
if (col > 0) {
auto loc = std::make_tuple(row, col - 1);
ExpandSeach(loc, guards, walls, distance, distances, toVisits);
}
if (col != (COLS - 1)) {
auto loc = std::make_tuple(row, col + 1);
ExpandSeach(loc, guards, walls, distance, distances, toVisits);
}
toVisits.pop_front();
}
}
return distances;
}
const LocAndDistMap GetDistances(const std::vector<std::vector<MuseumItem>> &museum)
{
LocationMap guards;
LocationMap walls;
if (!ParserMuseumMap(museum, guards, walls)) {
return LocAndDistMap();
}
const size_t ROWS = museum.size();
const size_t COLS = museum[0].size();
return GetDistances(ROWS, COLS, guards, walls);
}
// ********************************************************************************
// Test
// ********************************************************************************
#include <cassert>
void TestGetDistances()
{
{
const std::vector<std::vector<MuseumItem>> museum =
{{MuseumItem::OPEN, MuseumItem::OPEN, MuseumItem::OPEN, MuseumItem::OPEN, MuseumItem::OPEN},
{MuseumItem::OPEN, MuseumItem::OPEN, MuseumItem::OPEN, MuseumItem::OPEN, MuseumItem::OPEN},
{MuseumItem::OPEN, MuseumItem::OPEN, MuseumItem::GUARD, MuseumItem::OPEN, MuseumItem::OPEN},
{MuseumItem::OPEN, MuseumItem::OPEN, MuseumItem::OPEN, MuseumItem::OPEN, MuseumItem::OPEN},
{MuseumItem::OPEN, MuseumItem::OPEN, MuseumItem::OPEN, MuseumItem::OPEN, MuseumItem::OPEN} };
LocAndDistMap distances = GetDistances(museum);
assert(distances.find(std::make_tuple(0, 0))->second == 4);
assert(distances.find(std::make_tuple(1, 0))->second == 3);
assert(distances.find(std::make_tuple(2, 0))->second == 2);
assert(distances.find(std::make_tuple(3, 0))->second == 3);
assert(distances.find(std::make_tuple(4, 0))->second == 4);
assert(distances.find(std::make_tuple(0, 1))->second == 3);
assert(distances.find(std::make_tuple(1, 1))->second == 2);
assert(distances.find(std::make_tuple(2, 1))->second == 1);
assert(distances.find(std::make_tuple(3, 1))->second == 2);
assert(distances.find(std::make_tuple(4, 1))->second == 3);
assert(distances.find(std::make_tuple(0, 2))->second == 2);
assert(distances.find(std::make_tuple(1, 2))->second == 1);
assert(distances.find(std::make_tuple(2, 2)) == distances.end());
assert(distances.find(std::make_tuple(3, 2))->second == 1);
assert(distances.find(std::make_tuple(4, 2))->second == 2);
assert(distances.find(std::make_tuple(0, 3))->second == 3);
assert(distances.find(std::make_tuple(1, 3))->second == 2);
assert(distances.find(std::make_tuple(2, 3))->second == 1);
assert(distances.find(std::make_tuple(3, 3))->second == 2);
assert(distances.find(std::make_tuple(4, 3))->second == 3);
assert(distances.find(std::make_tuple(0, 4))->second == 4);
assert(distances.find(std::make_tuple(1, 4))->second == 3);
assert(distances.find(std::make_tuple(2, 4))->second == 2);
assert(distances.find(std::make_tuple(3, 4))->second == 3);
assert(distances.find(std::make_tuple(4, 4))->second == 4);
}
{
const std::vector<std::vector<MuseumItem>> museum =
{ { MuseumItem::OPEN, MuseumItem::WALL, MuseumItem::OPEN, MuseumItem::OPEN, MuseumItem::OPEN },
{ MuseumItem::OPEN, MuseumItem::WALL, MuseumItem::OPEN, MuseumItem::OPEN, MuseumItem::OPEN },
{ MuseumItem::OPEN, MuseumItem::WALL, MuseumItem::GUARD, MuseumItem::OPEN, MuseumItem::OPEN },
{ MuseumItem::OPEN, MuseumItem::WALL, MuseumItem::OPEN, MuseumItem::OPEN, MuseumItem::OPEN },
{ MuseumItem::OPEN, MuseumItem::WALL, MuseumItem::OPEN, MuseumItem::OPEN, MuseumItem::OPEN } };
LocAndDistMap distances = GetDistances(museum);
assert(distances.find(std::make_tuple(0, 0)) == distances.end());
assert(distances.find(std::make_tuple(1, 0)) == distances.end());
assert(distances.find(std::make_tuple(2, 0)) == distances.end());
assert(distances.find(std::make_tuple(3, 0)) == distances.end());
assert(distances.find(std::make_tuple(4, 0)) == distances.end());
assert(distances.find(std::make_tuple(0, 1)) == distances.end());
assert(distances.find(std::make_tuple(1, 1)) == distances.end());
assert(distances.find(std::make_tuple(2, 1)) == distances.end());
assert(distances.find(std::make_tuple(3, 1)) == distances.end());
assert(distances.find(std::make_tuple(4, 1)) == distances.end());
assert(distances.find(std::make_tuple(0, 2))->second == 2);
assert(distances.find(std::make_tuple(1, 2))->second == 1);
assert(distances.find(std::make_tuple(2, 2)) == distances.end());
assert(distances.find(std::make_tuple(3, 2))->second == 1);
assert(distances.find(std::make_tuple(4, 2))->second == 2);
assert(distances.find(std::make_tuple(0, 3))->second == 3);
assert(distances.find(std::make_tuple(1, 3))->second == 2);
assert(distances.find(std::make_tuple(2, 3))->second == 1);
assert(distances.find(std::make_tuple(3, 3))->second == 2);
assert(distances.find(std::make_tuple(4, 3))->second == 3);
assert(distances.find(std::make_tuple(0, 4))->second == 4);
assert(distances.find(std::make_tuple(1, 4))->second == 3);
assert(distances.find(std::make_tuple(2, 4))->second == 2);
assert(distances.find(std::make_tuple(3, 4))->second == 3);
assert(distances.find(std::make_tuple(4, 4))->second == 4);
}
{
const std::vector<std::vector<MuseumItem>> museum =
{ { MuseumItem::GUARD, MuseumItem::OPEN, MuseumItem::WALL, MuseumItem::OPEN, MuseumItem::OPEN },
{ MuseumItem::OPEN, MuseumItem::OPEN, MuseumItem::WALL, MuseumItem::OPEN, MuseumItem::OPEN },
{ MuseumItem::OPEN, MuseumItem::OPEN, MuseumItem::OPEN, MuseumItem::GUARD, MuseumItem::OPEN },
{ MuseumItem::GUARD, MuseumItem::OPEN, MuseumItem::WALL, MuseumItem::OPEN, MuseumItem::OPEN },
{ MuseumItem::OPEN, MuseumItem::OPEN, MuseumItem::WALL, MuseumItem::OPEN, MuseumItem::OPEN } };
LocAndDistMap distances = GetDistances(museum);
assert(distances.find(std::make_tuple(0, 0)) == distances.end());
assert(distances.find(std::make_tuple(1, 0))->second == 1);
assert(distances.find(std::make_tuple(2, 0))->second == 1);
assert(distances.find(std::make_tuple(3, 0)) == distances.end());
assert(distances.find(std::make_tuple(4, 0))->second == 1);
assert(distances.find(std::make_tuple(0, 1))->second == 1);
assert(distances.find(std::make_tuple(1, 1))->second == 2);
assert(distances.find(std::make_tuple(2, 1))->second == 2);
assert(distances.find(std::make_tuple(3, 1))->second == 1);
assert(distances.find(std::make_tuple(4, 1))->second == 2);
assert(distances.find(std::make_tuple(0, 2)) == distances.end());
assert(distances.find(std::make_tuple(1, 2)) == distances.end());
assert(distances.find(std::make_tuple(2, 2))->second == 1);
assert(distances.find(std::make_tuple(3, 2)) == distances.end());
assert(distances.find(std::make_tuple(4, 2)) == distances.end());
assert(distances.find(std::make_tuple(0, 3))->second == 2);
assert(distances.find(std::make_tuple(1, 3))->second == 1);
assert(distances.find(std::make_tuple(2, 3)) == distances.end());
assert(distances.find(std::make_tuple(3, 3))->second == 1);
assert(distances.find(std::make_tuple(4, 3))->second == 2);
assert(distances.find(std::make_tuple(0, 4))->second == 3);
assert(distances.find(std::make_tuple(1, 4))->second == 2);
assert(distances.find(std::make_tuple(2, 4))->second == 1);
assert(distances.find(std::make_tuple(3, 4))->second == 2);
assert(distances.find(std::make_tuple(4, 4))->second == 3);
}
}
No comments:
Post a Comment