## Facebook Interview Question for Android Engineers

Country: United States
Interview Type: Phone Interview

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

My solution: First find all guards which will take O(m*n), add it to queue as you find it.
Do BFS on the elements in queue. Total time complexity will be O(m*n). Also, I am using extra result array of size m*n, so space complexity will be O(m*n). m: no of rows and n: number of columns

``````class Solution {

class Position {
int i;
int j;
int distance;

public Position(int i, int j, int dist) {
this.i = i;
this.j = j;
this.distance = dist;
}

public Position() {
this.i = -1;
this.j = -1;
this.distance = -1;
}
}

public static void main(String[] args) {
char[][] matrix = { { 'o', 'o', 'o', 'g', 'o' }, { 'o', 'o', 'w', 'o', 'o' }, { 'o', 'g', 'o', 'o', 'w' },
{ 'o', 'w', 'g', 'o', 'o' }, { 'w', 'o', 'o', 'o', 'g' } };
Solution sol = new Solution();

int[][] result = sol.findDistance(matrix);

if (result == null) {
System.out.println("Invalid input Matrix");
}

for (int i = 0; i < result.length; i++) {
for (int j = 0; j < result[0].length; j++) {
System.out.print(result[i][j] + " ");
}
System.out.println();
}

}

public int[][] findDistance(char[][] matrix) {
if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
return null;
}
int[][] result = new int[matrix.length][matrix[0].length];

// finding Guards location and adding into queue
for (int i = 0; i < matrix.length; i++) {
for (int j = 0; j < matrix[0].length; j++) {
result[i][j] = -1;
if (matrix[i][j] == 'g') {
q.offer(new Position(i, j, 0));
result[i][j] = 0;
}
}
}

while (!q.isEmpty()) {
Position p = q.poll();
// result[p.i][p.j] = p.distance;
updateNeighbors(p, matrix, q, result);
}
return result;
}

public void updateNeighbors(Position p, char[][] matrix, Queue<Position> q, int[][] result) {
int[][] indexArray = { { -1, 0 }, { 0, 1 }, { 1, 0 }, { 0, -1 } };

for (int[] index : indexArray) {
if (isValid(p.i + index[0], p.j + index[1], matrix, result)) {
result[p.i + index[0]][p.j + index[1]] = p.distance + 1;
q.offer(new Position(p.i + index[0], p.j + index[1], p.distance + 1));
}
}
}

public boolean isValid(int i, int j, char[][] matrix, int[][] result) {
if ((i < 0 || i > matrix.length - 1) || (j < 0 || j > matrix[0].length - 1) || matrix[i][j] == 'w'
|| matrix[i][j] == 'g' || result[i][j] != -1) {
return false;
}
return true;
}
}``````

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

search guards first and do BST on each guard. Note if the new distance is larger or equal to the previously calculated distance we can break. This way the time complexity can be kept at column x row.

``````#include <vector>
#include <list>
#include <iostream>
using namespace std;

enum {W = -2, G = -1, O = 0};
struct OpenSpace {
int x;
int y;
int distance;
};

void findGuard (const vector<vector<int>> & matrix, list<pair<int, int>> & guards) {
for (int i = 0; i < matrix.size(); i++) {
for (int j = 0; j < matrix[0].size(); j++) {
if (matrix[i][j] == G) {
guards.push_back({i, j});
}
}
}
}

void inspect(vector<vector<int>> & matrix, list<OpenSpace> & queue) {
int curX = queue.front().x, curY = queue.front().y;
int distance = queue.front().distance;
queue.pop_front();
int shift[4][2] = {{1,0}, {-1,0}, {0,1}, {0,-1}};

for(int i = 0; i < 4; i++) {
int x = curX + shift[i][0];
int y = curY + shift[i][1];
if (x >= 0 && x < matrix.size() && y >= 0 && y < matrix[0].size()
&& matrix[x][y] != G && matrix[x][y] != W) {
if (matrix[x][y] == O || matrix[x][y] > distance + 1) {
matrix[x][y] = distance + 1;
queue.emplace_back(OpenSpace({x, y, distance+1}));
}
}
}
}

void findCoverage(vector<vector<int>> & matrix) {
list<pair<int, int>> guards;

findGuard(matrix, guards);
for (pair<int, int> xy : guards) {
list<OpenSpace> queue;

queue.emplace_back(OpenSpace({xy.first, xy.second, 0}));
// do BFS for each guard
while (!queue.empty()) {
inspect(matrix, queue);
}

}
}

int main() {
vector<vector<int>> matrix =
{{O, W, O, G, O},
{G, G, W, O, O},
{W, O, O, W, O},
{O, O, G, O, G}};

findCoverage(matrix);
for (auto row : matrix) {
for (auto i : row) {
printf("%2d ", i);
}
printf("\n");
}
}``````

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

My solution is a greedy algorithm that expands on every Guard cell updating neighbor distances, after that it does a top down and bottom-up expansion for updating open space cells. Time : O(n^2) space: O(n). Quite extensive code but it works.

``````public class MuseumDistances {

private static final int UNDISCOVERED = Integer.MAX_VALUE;
public static void main(String[] args) {
char[][] m = {{'O', 'W', 'G', 'O'},
{'O', 'W', 'W', 'O'},
{'O', 'W', 'O', 'O'},
{'O', 'O', 'O', 'G'}};
printMatrix(findDistanceMatrix(m));

char[][] m2 =
{
{'O', 'O', 'G', 'G', 'G'},
{'O', 'W', 'O', 'O', 'O'},
{'O', 'W', 'G', 'W', 'O'},
{'O', 'W', 'W', 'W', 'O'},
{'O', 'O', 'O', 'O', 'O'}};
printMatrix(findDistanceMatrix(m2));
}

public static int[][] findDistanceMatrix(char[][] m) {
int r[][] = new int[m.length][m.length];

// prepare distance matrix
for (int i = 0; i < r.length; i++) {
for (int j = 0; j < r.length; j++) {
if (m[i][j] == 'G') {
r[i][j] = 0;
} else if (m[i][j] == 'W') {
r[i][j] = -1;
} else {
r[i][j] = UNDISCOVERED;
}
}
}

// expand based on Guard cells
for (int i = 0; i < m.length; i++) {
for (int j = 0; j < m.length; j++) {
if (r[i][j] == 0) {
expandDistances(r, i, j);
}
}
}

// top down and bottom up sweep to update open cell neighbors
for (int i = m.length - 1; i >= 0; i--) {
for (int j = m.length - 1; j >= 0; j--) {
if (r[i][j] != 0 && r[i][j] != -1) {
expandDistancesNeighbors(r, i, j, false);
expandDistancesNeighbors(r, i, j, true);
}
}
}

return r;
}

private static void expandDistancesNeighbors(int[][] r, int x, int y, boolean rightDown) {
int i = x, j = y;
int dist = r[x][y];

if (rightDown) {
// expand down
i = x + 1;
while (i < r.length && r[i][j] != 0 && r[i][j] != -1) {
r[i][j] = Math.min(r[i][j], dist + 1);
dist++;
i++;
}

// expand right
i = x;
j = y + 1;
dist = r[x][y];
while (j < r.length && r[i][j] != 0 && r[i][j] != -1) {
r[i][j] = Math.min(r[i][j], dist + 1);
dist++;
j++;
}
} else {
// expand up
i = x - 1;
while (i >= 0 && r[i][j] != 0 && r[i][j] != -1) {
r[i][j] = Math.min(r[i][j], dist + 1);
dist++;
i--;
}

// expand left
i = x;
j = y - 1;
dist = r[x][y];
while (j >= 0 && r[i][j] != 0 && r[i][j] != -1) {
r[i][j] = Math.min(r[i][j], dist + 1);
dist++;
j--;
}

}
}

public static void printMatrix(int[][] a) {
for (int i = 0; i < a.length; i++) {
System.out.println();
for (int j = 0; j < a.length; j++) {
System.out.print(a[i][j] + " ");
}
}
}

public static void expandDistances(int[][] r, int x, int y) {
if (x >= r.length || y >= r.length || x < 0 || y < 0 || r[x][y] == -1) {
return;
} else {
int i = x, j = y;
int dist = 1;

// expand up
i = x - 1;
while (i >= 0 && r[i][j] != 0 && r[i][j] != -1) {
r[i][j] = Math.min(r[i][j], dist);
dist++;
i--;
}

// expand down
i = x + 1;
dist = 1;
while (i < r.length && r[i][j] != 0 && r[i][j] != -1) {
r[i][j] = Math.min(r[i][j], dist);
dist++;
i++;
}

// expand right
i = x;
j = y + 1;
dist = 1;
while (j < r.length && r[i][j] != 0 && r[i][j] != -1) {
r[i][j] = Math.min(r[i][j], dist);
dist++;
j++;
}

// expand left
j = y - 1;
dist = 1;
while (j >= 0 && r[i][j] != 0 && r[i][j] != -1) {
r[i][j] = Math.min(r[i][j], dist);
dist++;
j--;
}
}
}
}``````

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

The following code iterates over every entry in the matrix, and performs BFS outwards at each entry, returning the distance as soon as it encounters a guard entry.

``````from collections import deque

def guards(m):
d = empty_copy(m)
for i in range(0, len(m)):
for j in range(0, len(m[i])):
d[i][j] = guards_dist(m, i, j)
format(m, d)
return d

def empty_copy(m):
res = []
for i in range(0, len(m)):
res.append([])
for j in range(0, len(m[i])):
res[i].append(None)
return res

def format(m, d):
for i in range(0, len(m)):
for j in range(0, len(m[i])):
if m[i][j] == "G" or m[i][j] == "W":
d[i][j] = m[i][j]
else:
d[i][j] = str(d[i][j])

def guards_dist(m, i, j):
seen = {}
q = deque([(i, j, 0)])
while len(q) > 0:
i, j, dist = q.popleft()
if i < 0 or i >= len(m) or j < 0 or j >= len(m[i]) or (i, j) in seen:
continue
seen[(i, j)] = True
if m[i][j] == "G":
return dist
elif m[i][j] == "W":
continue
else:
q.append((i - 1, j - 1, dist + 1))
q.append((i - 1, j, dist + 1))
q.append((i - 1, j + 1, dist + 1))
q.append((i, j - 1, dist + 1))
q.append((i, j + 1, dist + 1))
q.append((i + 1, j - 1, dist + 1))
q.append((i + 1, j, dist + 1))
q.append((i + 1, j + 1, dist + 1))
return 0

m = [
["O", "O", "O", "O", "O", "O", "O", "W", "O", "G"],
["O", "O", "O", "O", "O", "O", "O", "W", "O", "O"],
["O", "O", "O", "O", "W", "O", "O", "W", "O", "O"],
["O", "O", "O", "O", "W", "O", "O", "W", "W", "W"],
["O", "O", "O", "O", "W", "O", "G", "O", "O", "O"],
["W", "W", "W", "O", "W", "O", "O", "O", "O", "O"],
["O", "O", "O", "O", "W", "O", "O", "O", "O", "O"],
["O", "O", "O", "O", "W", "O", "O", "O", "O", "O"],
["O", "O", "O", "O", "W", "O", "O", "O", "O", "O"],
["G", "O", "O", "O", "W", "O", "O", "O", "O", "O"],
]

for i in guards(m):
print(i)``````

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

Iterating over the entire matrix and using BFS to find the nearest guard is the way to go. O(n^2) where n is the number of entries in the matrix.

``````from collections import deque

def guards(m):
d = empty_copy(m)
for i in range(0, len(m)):
for j in range(0, len(m[i])):
d[i][j] = guards_dist(m, i, j)
format(m, d)
return d

def empty_copy(m):
res = []
for i in range(0, len(m)):
res.append([])
for j in range(0, len(m[i])):
res[i].append(None)
return res

def format(m, d):
for i in range(0, len(m)):
for j in range(0, len(m[i])):
if m[i][j] == "G" or m[i][j] == "W":
d[i][j] = m[i][j]
else:
d[i][j] = str(d[i][j])

def guards_dist(m, i, j):
seen = {}
q = deque([(i, j, 0)])
while len(q) > 0:
i, j, dist = q.popleft()
if i < 0 or i >= len(m) or j < 0 or j >= len(m[i]) or (i, j) in seen:
continue
seen[(i, j)] = True
if m[i][j] == "G":
return dist
elif m[i][j] == "W":
continue
else:
q.append((i - 1, j - 1, dist + 1))
q.append((i - 1, j, dist + 1))
q.append((i - 1, j + 1, dist + 1))
q.append((i, j - 1, dist + 1))
q.append((i, j + 1, dist + 1))
q.append((i + 1, j - 1, dist + 1))
q.append((i + 1, j, dist + 1))
q.append((i + 1, j + 1, dist + 1))
return 0

m = [
["O", "O", "O", "O", "O", "O", "O", "W", "O", "G"],
["O", "O", "O", "O", "O", "O", "O", "W", "O", "O"],
["O", "O", "O", "O", "W", "O", "O", "W", "O", "O"],
["O", "O", "O", "O", "W", "O", "O", "W", "W", "W"],
["O", "O", "O", "O", "W", "O", "G", "O", "O", "O"],
["W", "W", "W", "O", "W", "O", "O", "O", "O", "O"],
["O", "O", "O", "O", "W", "O", "O", "O", "O", "O"],
["O", "O", "O", "O", "W", "O", "O", "O", "O", "O"],
["O", "O", "O", "O", "W", "O", "O", "O", "O", "O"],
["G", "O", "O", "O", "W", "O", "O", "O", "O", "O"],
]

for i in guards(m):
print(i)``````

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

Start from the guards, and calculate shortest path with BFS to each room. I think that problem has been given in Google before

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

Space complexity: rowxcol is unavoidable as new matrix is needed. For simplicity, I am using row+2 x col+2 matrix as internal buffer. And output is generated from central part of rowxcol. In addition, I use similar size boolean matrix to track visited node.
So, space = O(rowXcol)
Time complexity: For every guard, BFS is performed. So, O(nrc) where n = number of gurads, r = rows, c = columns

``````struct cellNode{
pair<int, int> pos;
int depth;
};
void bfs(vector<string> & os, vector<vector<bool>> visited, int y, int x){
int rows = os.size()-2;
int cols = os[0].length()-2;
//cout << "DBG: row x col = " << rows << ", " << cols << endl;
vector<pair<int, int>> exp = {{0,-1},{0,1},{-1,0},{1,0}};
queue<cellNode> posQ;
cellNode cell;
cell.depth = 0;
cell.pos.first = y;
cell.pos.second = x;
posQ.push(cell);
visited[y][x] = true;
int i , j;
while(!posQ.empty()){
cellNode cell = posQ.front();
int y = cell.pos.first;
int x = cell.pos.second;
int d = cell.depth;
posQ.pop();
if(os[y][x]!='W' && os[y][x]!='G'){
if(os[y][x]=='O'){
os[y][x] = '0' + d;
}else{
int old = os[y][x] - '0';
if(old>d){
os[y][x] = '0' + d;
}
}
}
//cout << "DBG: current poped = " << y << ", " << x << endl;
for(int p = 0 ; p<exp.size(); ++p){
int i = exp[p].first;
int j = exp[p].second;
int posy = y+i, posx = x+j;
if(!visited[posy][posx] && os[posy][posx]!='W' && os[posy][posx]!='G' && posy!=0 && posx!=0 && posy!=(rows+1) && posx!=(cols+1)){
cellNode cell;
cell.pos.first = posy;
cell.pos.second = posx;
cell.depth = d + 1;
posQ.push(cell);
visited[posy][posx] = true;
}
}
}
}

vector<string> guardMatrix(vector<string> map){
int rows = map.size();
int cols = map[0].length();
string temp(cols+2,'W');
vector<string> os(rows+2, temp);
for(int i = 0 ; i < rows ; ++i){
for(int j = 0 ; j < cols ; ++j){
os[i+1][j+1] = map[i][j];
}
}
for(int i = 0 ; i < rows ; ++i){
for(int j = 0 ; j < cols ; ++j){
if(map[i][j]=='G'){
//cout << "DBG: gurad = " << i << ", " << j << endl;
vector<vector<bool>> visited(rows+2, vector<bool>(cols+2,false));
bfs(os, visited, i+1, j+1);
}
}
}
vector<string> result = map;
for(int i = 0 ; i < rows ; ++i){
for(int j = 0 ; j < cols ; ++j){
if(map[i][j]=='O')
result[i][j] = os[i+1][j+1];
}
}
return result;
}

int main(){
/*vector<string> map = {"WWWW",
"GOOO",
"OWWG",
"OWOO",};*/
/*vector<string> map = {"GOWWO",
"OWOOO",
"OOWWO",
"OOOOG"}; */
vector<string> map = {"OOGOW",
"OOOOO",
"OWGWO",
"OOOOO",
"GOWOO"};
vector<string> newMap = guardMatrix(map);
for(auto & s : newMap)
cout << s << endl;
}``````

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

``````class Solution {

class Position{
int i;
int j;
int distance;

public Position(int i, int j, int dist){
this.i = i;
this.j = j;
this.distance = dist;
}

public Position(){
this.i = -1;
this.j = -1;
this.distance = -1;
}
}

public static void main(String[] args) {
char[][] matrix = {{'o','o','o','g','o'},
{'o','o','w','o','o'},
{'o','g','o','o','w'},
{'o','w','g','o','o'},
{'w','o','o','o','g'}
};
Solution sol = new Solution();

int[][] result = sol.findDistance(matrix);

if(result == null) {
System.out.println("Invalid input Matrix");
}

for(int i=0; i < result.length; i++) {
for(int j=0; j < result[0].length; j++) {
System.out.print(result[i][j] +  " ");
}
System.out.println();
}

}

public int[][] findDistance(char[][] matrix){
if(matrix == null || matrix.length == 0 || matrix[0].length == 0) {
return null;
}
int[][] result = new int[matrix.length][matrix[0].length];

// finding Guards location and adding into queue
for(int i=0; i < matrix.length; i++) {
for(int j=0; j < matrix[0].length; j++) {
if(matrix[i][j] =='g'){
q.offer(new Position(i, j, 0));
}
result[i][j] = -1;
}
}

while(!q.isEmpty()) {
Position p = q.poll();
result[p.i][p.j] = p.distance;
updateNeighbors(p, matrix, q, result);
}
return result;
}

public void updateNeighbors(Position p, char[][] matrix, Queue<Position> q, int[][] result) {
int[][] indexArray = {{-1,0},{0,1},{1,0},{0,-1}};

for(int[] index: indexArray) {
if(isValid(p.i+index[0], p.j+index[1], matrix, result)) {
result[p.i+index[0]][p.j + index[1]] = p.distance + 1;
q.offer(new Position(p.i+index[0], p.j+index[1], p.distance+1));
}
}
}

public boolean isValid(int i, int j, char[][] matrix, int[][] result) {
if((i < 0 || i > matrix.length -1) || (j < 0 || j > matrix[0].length -1) || matrix[i][j] == 'w' || result[i][j] != -1) {
return false;
}
return true;
}
}``````

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

My Solution uses branch and bound (B&B) with dynamic programming using distance travelled to estimate the closest guard. drawback is sorting
time complexity and size is 0(n^2).

``````package com.test;

import java.util.ArrayList;
import java.util.Collections;

public class DPMuseumMatrix {

static String SPACE = "O";
static String GUARD = "G";
static String WALL = "W";
String[][] museum;

public DPMuseumMatrix(String[][] museum) {
this.museum = museum;
}

public String[][] getDistanceMatrix() {
for (int i = 0; i < museum.length; i++)
for (int j = 0; j < museum[0].length; j++)
if (museum[i][j].equals(SPACE))
findGuard(i, j);

return museum;
}

protected void findGuard(int x, int y) {
ArrayList<Element> traveledPaths = new ArrayList<Element>();
ArrayList<Element> queue = new ArrayList<Element>();
Element ret = null;
while (true) {
if (isGuard(queue.get(0))) {
ret = queue.remove(0).parent;
break;
} else {
Element parent = queue.remove(0);
if (parent == null)
break;
Collections.sort(queue);
}
}
if (ret != null)
updateMatrix(ret);
}

protected boolean isGuard(Element e) {
return museum[e.x][e.y].equals(GUARD);
}

protected void updateMatrix(Element path) {
int distance = 1;
while (path != null) {
if (museum[path.x][path.y] == "O")
museum[path.x][path.y] = "" + distance;
else if (isDistance(museum[path.x][path.y]))
distance = Integer.parseInt(museum[path.x][path.y]);
path = path.parent;
distance++;
}
}

protected boolean isDistance(String str) {
try{
Integer.parseInt(str);
return true;
} catch(Exception e) {
return false;
}
}

Element e) {
ArrayList<Element> l = new ArrayList<Element>();
if (e.y + 1 < museum[0].length && isValidChild(traveledPaths, e.x, e.y + 1))
l.add(new Element(e, e.x, e.y + 1));
if (e.x + 1 < museum.length && isValidChild(traveledPaths, e.x + 1, e.y))
l.add(new Element(e, e.x + 1, e.y));
if (e.y - 1 >= 0 && isValidChild(traveledPaths, e.x, e.y - 1))
l.add(new Element(e, e.x, e.y - 1));
if (e.x - 1 >= 0 && isValidChild(traveledPaths, e.x - 1, e.y))
l.add(new Element(e, e.x - 1, e.y));
return l;
}

protected boolean isValidChild(ArrayList<Element> traveledPaths, int x, int y) {
//check if position is in a travelled path
for (Element e : traveledPaths)
if (e.x == x && e.y == y)
return false;
//element is a wall
return !museum[x][y].equals(WALL);
}

///Linked list to handle paths to goal
public class Element implements Comparable<Element> {
int x;
int y;
Integer distanceTraveled;
Element parent;

public Element(int x, int y) {
this.x = x;
this.y = y;
distanceTraveled = 1;
}

public Element(Element parent, int x, int y) {
this(x, y);
distanceTraveled += parent.distanceTraveled;
this.parent = parent;
}

@Override
public int compareTo(Element e) {
return this.distanceTraveled.compareTo(e.distanceTraveled);
}
}

public static void main(String[] args) {
String[][] museum = {
{ "O", "O", "W", "G", "O" },
{ "O", "O", "O", "O", "W" },
{ "O", "W", "O", "O", "O" },
{ "W", "W", "O", "W", "W" },
{ "G", "W", "O", "W", "G" },
{ "O", "O", "O", "O", "O" } };
print("original", museum);
String[][] ret = new DPMuseumMatrix(museum).getDistanceMatrix();
print("result", ret);
}

public static void print(String label, String[][] museum) {
System.out.println(label);
for (int i = 0; i < museum.length; i++) {
for (int j = 0; j < museum[0].length; j++)
System.out.print(museum[i][j] + " ");
System.out.println();
}
System.out.println();
}

}``````

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

``````def printM(m):
for row in m:
for e in row:
print('{}\t'.format(str(e)), end='')
print('')
print('')

def handle_element(element, count, replaced):
if element == 'G':
count = 0
elif element == 'W':
count = -1
elif element == 'O':
if count > -1:
count += 1
element = count
replaced = True
else: # number
if count > -1:
count += 1
if count < element:
element = count
replaced = True
if element < count:
count = element
else:
count = element
return element, count, replaced

def replace_once(m):
replaced = False
iRanges = [list(range(len(m))), list(reversed(range(len(m))))]
jRanges = [list(range(len(m[0]))), list(reversed(range(len(m[0]))))]
for i in iRanges[0]:
for jRange in jRanges: # twice
count = -1
for j in jRange:
m[i][j], count, replaced = handle_element(m[i][j], count, replaced)
for j in jRanges[0]:
for iRange in iRanges: # twice
count = -1
for i in iRange:
m[i][j], count, replaced = handle_element(m[i][j], count, replaced)
return replaced, m

def replace(m):
replaced = True
while replaced:
replaced, m = replace_once(m)
printM(m)

m = [
["O", "O", "O", "O", "O", "O", "O", "W", "O", "G"],
["O", "O", "O", "O", "O", "O", "O", "W", "O", "O"],
["O", "O", "O", "O", "W", "O", "O", "W", "O", "O"],
["O", "O", "O", "O", "W", "O", "O", "W", "W", "W"],
["O", "O", "O", "O", "W", "O", "G", "O", "O", "O"],
["W", "W", "W", "O", "W", "O", "O", "O", "O", "O"],
["O", "O", "O", "O", "W", "O", "O", "O", "O", "O"],
["O", "O", "O", "O", "W", "O", "O", "O", "O", "O"],
["O", "O", "O", "O", "W", "O", "O", "O", "O", "O"],
["G", "O", "O", "O", "W", "O", "O", "O", "O", "O"],
]

printM(m)
replace(m)``````

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

Simple algorithm: on each iteration we check the nearest cells and set the current value as smallest + 1. Then just iterate until there's no updates.

``````from pprint import pprint

m0 = [
['W', 'W', 'O', 'W', 'G'],
['W', 'W', 'O', 'O', 'O'],
['O', 'O', 'O', 'W', 'O'],
['O', 'W', 'W', 'W', 'O'],
['O', 'O', 'O', 'W', 'O'],
]

m1 = [
["O", "O", "O", "O", "O", "O", "O", "W", "O", "G"],
["O", "O", "O", "O", "O", "O", "O", "W", "O", "O"],
["O", "O", "O", "O", "W", "O", "O", "W", "O", "O"],
["O", "O", "O", "O", "W", "O", "O", "W", "W", "W"],
["O", "O", "O", "O", "W", "O", "G", "O", "O", "O"],
["W", "W", "W", "O", "W", "O", "O", "O", "O", "O"],
["O", "O", "O", "O", "W", "O", "O", "O", "O", "O"],
["O", "O", "O", "O", "W", "O", "O", "O", "O", "O"],
["O", "O", "O", "O", "W", "O", "O", "O", "O", "O"],
["G", "O", "O", "O", "W", "O", "O", "O", "O", "O"],
]

m2 = [
["O", "O", "O", "O", "O", "O", "O", "W", "O", "G"],
["O", "O", "O", "O", "O", "O", "O", "W", "O", "O"],
["O", "O", "O", "O", "W", "O", "O", "W", "O", "O"],
["O", "O", "O", "O", "W", "O", "O", "W", "W", "W"],
["O", "O", "O", "O", "W", "O", "G", "O", "O", "O"],
["W", "W", "W", "O", "W", "O", "O", "O", "O", "O"],
["O", "O", "O", "O", "W", "O", "O", "O", "O", "O"],
["O", "O", "O", "O", "W", "O", "O", "O", "O", "O"],
["O", "O", "O", "O", "W", "O", "O", "O", "O", "O"],
["G", "O", "O", "O", "W", "O", "O", "O", "O", "O"],
]

def calculate_museum(museum):
size = len(museum)

for x in xrange(size):
for y in xrange(size):
res = None
if museum[x][y] is 'O':
if x > 0:
res = test_cell(museum[x-1][y], museum[x][y])
if res:
museum[x][y] = res
if x < (size-1):
res = test_cell(museum[x+1][y], museum[x][y])
if res:
museum[x][y] = res
if y > 0:
res = test_cell(museum[x][y-1], museum[x][y])
if res:
museum[x][y] = res
if y < (size-1):
res = test_cell(museum[x][y+1], museum[x][y])
if res:
museum[x][y] = res

calculate_museum(museum)

def test_cell(cell, cur):
if cell is 'G':
return 1
if isinstance(cell, int):
if cur and cell > cur:
return None
return cell+1
return None

pprint(m0)
calculate_museum(m0)
print("Result:")
pprint(m0)
print

pprint(m1)
calculate_museum(m1)
print("Result:")
pprint(m1)
print

pprint(m2)
calculate_museum(m2)
print("Result:")
pprint(m2)``````

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

``````#include <vector>
#include <list>
#include <iostream>
using namespace std;

enum {W = -2, G = -1, O = 0};
struct OpenSpace {
int x;
int y;
int distance;
};

void findGuard (const vector<vector<int>> & matrix, list<pair<int, int>> & guards) {
for (int i = 0; i < matrix.size(); i++) {
for (int j = 0; j < matrix[0].size(); j++) {
if (matrix[i][j] == G) {
guards.push_back({i, j});
}
}
}
}

void inspect(vector<vector<int>> & matrix, list<OpenSpace> & queue) {
int curX = queue.front().x, curY = queue.front().y;
int distance = queue.front().distance;
queue.pop_front();
int shift[4][2] = {{1,0}, {-1,0}, {0,1}, {0,-1}};

for(int i = 0; i < 4; i++) {
int x = curX + shift[i][0];
int y = curY + shift[i][1];
if (x >= 0 && x < matrix.size() && y >= 0 && y < matrix[0].size()
&& matrix[x][y] != G && matrix[x][y] != W) {
if (matrix[x][y] == O || matrix[x][y] > distance + 1) {
matrix[x][y] = distance + 1;
queue.emplace_back(OpenSpace({x, y, distance+1}));
}
}
}
}

void findCoverage(vector<vector<int>> & matrix) {
list<pair<int, int>> guards;

findGuard(matrix, guards);
for (pair<int, int> xy : guards) {
list<OpenSpace> queue;

queue.emplace_back(OpenSpace({xy.first, xy.second, 0}));
// do BFS for each guard
while (!queue.empty()) {
inspect(matrix, queue);
}

}
}

int main() {
vector<vector<int>> matrix =
{{O, W, O, G, O},
{G, G, W, O, O},
{W, O, O, W, O},
{O, O, G, O, G}};

findCoverage(matrix);
for (auto row : matrix) {
for (auto i : row) {
printf("%2d ", i);
}
printf("\n");
}
}``````

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

A solution based on graph and breadth-first traverse is present here: cpluspluslearning-petert.blogspot.co.uk/2016/06/data-structure-and-algorithm-find.html

Test code

``````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);
}
}``````

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

I also iterate over each guard (as I find them using a generator).
For each guard I do a BFS and update any distances in place.

It won't update distances if it is a wall or there's a shorter distance at that location already (near another guard).

A little optimisation that, depending on the configuration of the board, might save some time on average is:
Don't explore neighbours of locations that already have a shorter distance to another guard. Because of the BFS expansion, it means it isn't possible to find another location with a shorter distance afterwards. (p.s. that's an advantage over doing DFS here).

Here's my Python solution:

``````class GuardDistance(object):
def __init__(self, matrix):
self._matrix = matrix
self._size = len(matrix)

def matrix(self):
return self._matrix

def calculate_distances(self):
for gx, gy in self._find_guards():
visited = set()
frontier = self._neighbours(gx, gy, 0, visited)
while frontier:
(x, y), distance = frontier.pop(0)
if self._update(x, y, distance):
frontier += self._neighbours(x, y, distance, visited)

def _find_guards(self):
return ((x, y) for x in xrange(self._size)
for y in xrange(self._size)
if self._matrix[x][y] == 'G')

def _neighbours(self, x, y, distance, visited):
neighbours = []
for dx, dy in [(-1, 0), (0, -1), (1, 0), (0, 1)]:
nx, ny = x + dx, y + dy
if self._valid_location(nx, ny) and (nx, ny) not in visited:
neighbours.append(((nx, ny), distance + 1))
return neighbours

def _valid_location(self, x, y):
return 0 <= x < self._size and 0 <= y < self._size

def _update(self, x, y, distance):
value = self._matrix[x][y]
if str(value) not in 'GW' and (value == 'O' or value >= distance):
self._matrix[x][y] = distance
return True
else:
return False

# ere's some code to run this
solution = GuardDistance([['O','O','O','G'],
['O','W','W','W'],
['O','W','G','W'],
['O','O','O','O']])
solution.calculate_distances()
print solution.matrix()``````

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

Iterate over each guard and BFS. For every new BFS level the total distance increase by one, don't include neighbors that are walls or have lesser value than the current distance.

Diagonal moves are valid.

``````import collections

def initialize(m, dest, q):
value_map = {'g': 0, 'o': float('inf'), 'w': -1}
for i in range(len(m)):
dest.append([0] * len(m[0]))
for j in range(len(m[0])):
dest[i][j] = value_map[m[i][j].lower()]
if m[i][j].lower() == 'g':
q.append((i, j))

def guard_distance(m):
result = []
q = collections.deque()
# Valid moves are all directions (diagonals included)
surroundings = [(-1, -1), (-1, 0), (-1, +1), (0, -1),
(0, +1), (+1, 0), (+1, -1), (+1, +1)]

initialize(m, result, q)
dist = 1
while q:
# Empty first level before increasing
# distance
for _ in range(len(q)):
curr = q.popleft()
for coord in surroundings:
i = curr[0] + coord[0]
j = curr[1] + coord[1]
try:
if result[i][j] > dist:
result[i][j] = dist
q.append((i, j))
except IndexError:
# Hit matrix borders
pass
dist += 1
return result

m = [['g', 'w', 'o', 'o', 'w'],
['o', 'w', 'o', 'W', 'w'],
['o', 'o', 'o', 'o', 'w'],
['O', 'w', 'o', 'G', 'w'],
['G', 'w', 'w', 'o', 'w']]

print '\n'.join(str(x) for x in guard_distance(m))``````

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

Lengthy but should do the work. A lot of hard coding but you get the point.

``````char m2[5][5] = {
{'O', 'O', 'G', 'G', 'G'},
{'O', 'W', 'O', 'O', 'O'},
{'O', 'W', 'G', 'W', 'O'},
{'O', 'W', 'W', 'W', 'O'},
{'O', 'O', 'O', 'O', 'O'}};

int dist[5][5] = {
{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}};

int least_min_nearby_i_j(int i, int j){
if (i>=0 && i<5 && j>=0 && j<5){
if (dist[i][j]>0){
return dist[i][j]+1;
}
return 1000;
}
return 1000;
}

int least_min_nearby(int i, int j, int iter){
int left = 0, right =0, top=0, bottom=0, min_i=0,min_j=0,min=0;
//printf("i=%d,j=%d\n",i,j);
left = least_min_nearby_i_j(i-1,j);
right = least_min_nearby_i_j(i+1,j);
top = least_min_nearby_i_j(i,j-1);
bottom = least_min_nearby_i_j(i,j+1);
min_i = (left < right) ? left : right;
min_j = (top < bottom) ? top : bottom;
min = (min_i < min_j) ? min_i : min_j;
if (min > iter){
return 0;
}
return min;
}

int check_i_j(int i, int j){
if (i>=0 && i<5 && j>=0 && j<5){
if (m2[i][j] == 'G'){
return 1;
}
}
return 0;
}

int check_nearby(int i,int j){
int left = 0, right =0, top=0, bottom=0;
//printf("i=%d,j=%d\n",i,j);
left = check_i_j(i-1,j);
right = check_i_j(i+1,j);
top = check_i_j(i,j-1);
bottom = check_i_j(i,j+1);
//printf("%d%d%d%d\n",top,left,right,bottom);
if (left || right || top || bottom)
return 1;
return 0;
}

int main(void) {

int i=0,j=0,count=0,iter=0;

for (i=0;i<5;i++)
{
for (j=0;j<5;j++)
{
switch (m2[i][j])
{
case 'G':	dist[i][j] = -1;
break;
case 'W':	dist[i][j] = -2;
break;
case 'O':	dist[i][j] = check_nearby(i,j);
break;
}
if (dist[i][j] == 0){
count++;
}
}
}
iter=1;
while (count > 0){
iter++;
count = 0;
for (i=0;i<5;i++)
{
for (j=0;j<5;j++)
{
if (dist[i][j] == 0){
dist[i][j] = least_min_nearby(i,j,iter);
}
if (dist[i][j] == 0){
count++;
}
}
}
}
for (i=0;i<5;i++){
for (j=0;j<5;j++)
printf("%02d ", dist[i][j]);
printf("\n");
}
return 0;
}``````

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

``````char m2[5][5] = {
{'O', 'O', 'G', 'G', 'G'},
{'O', 'W', 'O', 'O', 'O'},
{'O', 'W', 'G', 'W', 'O'},
{'O', 'W', 'W', 'W', 'O'},
{'O', 'O', 'O', 'O', 'O'}};

int dist[5][5] = {
{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}};

int least_min_nearby_i_j(int i, int j){
if (i>=0 && i<5 && j>=0 && j<5){
if (dist[i][j]>0){
return dist[i][j]+1;
}
return 1000;
}
return 1000;
}

int least_min_nearby(int i, int j, int iter){
int left = 0, right =0, top=0, bottom=0, min_i=0,min_j=0,min=0;
//printf("i=%d,j=%d\n",i,j);
left = least_min_nearby_i_j(i-1,j);
right = least_min_nearby_i_j(i+1,j);
top = least_min_nearby_i_j(i,j-1);
bottom = least_min_nearby_i_j(i,j+1);
min_i = (left < right) ? left : right;
min_j = (top < bottom) ? top : bottom;
min = (min_i < min_j) ? min_i : min_j;
if (min > iter){
return 0;
}
return min;
}

int check_i_j(int i, int j){
if (i>=0 && i<5 && j>=0 && j<5){
if (m2[i][j] == 'G'){
return 1;
}
}
return 0;
}

int check_nearby(int i,int j){
int left = 0, right =0, top=0, bottom=0;
//printf("i=%d,j=%d\n",i,j);
left = check_i_j(i-1,j);
right = check_i_j(i+1,j);
top = check_i_j(i,j-1);
bottom = check_i_j(i,j+1);
//printf("%d%d%d%d\n",top,left,right,bottom);
if (left || right || top || bottom)
return 1;
return 0;
}

int main(void) {

int i=0,j=0,count=0,iter=0;

for (i=0;i<5;i++)
{
for (j=0;j<5;j++)
{
switch (m2[i][j])
{
case 'G':	dist[i][j] = -1;
break;
case 'W':	dist[i][j] = -2;
break;
case 'O':	dist[i][j] = check_nearby(i,j);
break;
}
if (dist[i][j] == 0){
count++;
}
}
}
iter=1;
while (count > 0){
iter++;
count = 0;
for (i=0;i<5;i++)
{
for (j=0;j<5;j++)
{
if (dist[i][j] == 0){
dist[i][j] = least_min_nearby(i,j,iter);
}
if (dist[i][j] == 0){
count++;
}
}
}
}
for (i=0;i<5;i++){
for (j=0;j<5;j++)
printf("%02d ", dist[i][j]);
printf("\n");
}
return 0;
}``````

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

Can you explain the problem with an example please?

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

def replace_with_distance(M, guard_x, guard_y, shortest):
if not guard_x >= len(M) and not guard_y >= len(M) \
and not guard_x < 0 and not guard_y < 0 \
and M[guard_x][guard_y] != 'W':
if M[guard_x][guard_y] == 'G':
M[guard_x][guard_y] = 0
replace_with_distance(M, guard_x + 1, guard_y, 0)
replace_with_distance(M, guard_x, guard_y + 1, 0)
replace_with_distance(M, guard_x - 1, guard_y, 0)
replace_with_distance(M, guard_x, guard_y - 1, 0)
elif M[guard_x][guard_y] == 'O' or M[guard_x][guard_y] > shortest + 1:
M[guard_x][guard_y] = shortest + 1
replace_with_distance(M, guard_x + 1, guard_y, shortest + 1)
replace_with_distance(M, guard_x, guard_y + 1, shortest + 1)
replace_with_distance(M, guard_x - 1, guard_y, shortest + 1)
replace_with_distance(M, guard_x, guard_y - 1, shortest + 1)

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

My method requires to traverse through the matrix, update the steps as long as it is an open space by (1) look through surrounding neighbors for guards (2) looks for open space with steps updated and simply add them up (3) look for open space and move towards there, therefore incrementing the steps. Time complexity is O(n^2).

``````public static void main(String args[]) {
char[][] arr = {{'O', 'O', 'O', 'G'}, {'W', 'G', 'O', 'O'}, {'O', 'O', 'W', 'G'}, {'W', 'O', 'O', 'O'}};

arr = updateMatrix(arr);

for (int i=0; i<arr.length; i++) {
for (int j=0; j<arr[i].length; j++) {

if (j==0)
System.out.print(arr[i][j]);
else
System.out.print(" "+arr[i][j]);
}
System.out.print("\n");
}
}

private static char[][] updateMatrix (char arr[][]){

for (int i=0; i<arr.length; i++) {
for (int j=0; j<arr[i].length; j++) {
if (arr[i][j] == 'O') {
int step = 1;

step += lookSurrounding(arr, i, j, arr.length);

//to convert to int - RADIX = 10
arr[i][j] = Character.forDigit(step, 10);
}
}
}

return arr;
}

private static int lookSurrounding(char arr[][],
int row,
int col,
int arraySize) {

//represent Up, Down, Left, Right
Character[] surroundingVal = {'E', 'E', 'E', 'E'};
int existingStep = -1;

//up
if (row - 1 >= 0) {
surroundingVal[0] = arr[row-1][col];
existingStep = Character.isDigit(surroundingVal[0]) && Character.getNumericValue(surroundingVal[0]) > existingStep
? Character.getNumericValue(surroundingVal[0]) : existingStep;
}

//down
if (row + 1 < arraySize) {
surroundingVal[1] = arr[row + 1][col];
existingStep = Character.isDigit(surroundingVal[1]) && Character.getNumericValue(surroundingVal[1]) > existingStep
? Character.getNumericValue(surroundingVal[1]) : existingStep;
}
//left
if (col - 1 >= 0) {
surroundingVal[2] = arr[row][col - 1];
existingStep = Character.isDigit(surroundingVal[2]) && Character.getNumericValue(surroundingVal[2]) > existingStep
? Character.getNumericValue(surroundingVal[2]) : existingStep;
}
//right
if (col + 1 < arraySize) {
surroundingVal[3] = arr[row][col+1];
existingStep = Character.isDigit(surroundingVal[3]) && Character.getNumericValue(surroundingVal[3]) > existingStep
? Character.getNumericValue(surroundingVal[3]) : existingStep;
}

if (Arrays.asList(surroundingVal).contains('G'))
return 0;
else if (existingStep > -1 )
return existingStep;
else if (Arrays.asList(surroundingVal).contains('O')) {

int step = 1;
int index = Arrays.asList(surroundingVal).indexOf('O');
int newRow = row, newCol = col;
if (index == 0)
newRow = row - 1;
else if (index == 1)
newRow = row + 1;
else if (index == 2)
newCol = col - 1;
else if (index == 3)
newCol = col + 1;

step += lookSurrounding(arr, newRow, newCol, arraySize);

return step;
}

//cater for error

return 0;
}``````

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

BFS solution starting at the guards. O(n^2) time and space:

``````class Square{
int x, y, distance;

Square(int x, int y, int distance){
this.x = x;
this.y = y;
this.distance = distance;
}

}

static int[][] DIRECTIONS = new int[]{{0, 1}, {0, -1}, {1, 0}, {-1,0}};

public int[][] getDistances(char[][] museum){
int n = museum.length;
int m = museum[0].length;
if(n == 0 || m == 0)
return null;

boolean[][] visited = new boolean[n][m];
int[][] result = new int[n][m];
Queue<Square> squares = new Queue<Square>();

//BFS starting at the guards
for(int i = 0; i < n; i++){
for(int j = 0; j < m; j++){
if(museum[i][j] == ‘G’){
visited[i][j] = true;
}else{
if(museum[i][j] == ‘W’){
visited[i][j] = true;
}
//By default no way to reach a guard
result[i][j] = -1;
}
}
}

while(!squares.isEmpty()){
Square square = squares.pop();
result[square.x][square.y] = square.distance;

for(int[] direction : directions]){
int x = square.x + direction[0];
int y = square.y + direction[1];
if(x >= 0 && x < n && y >= 0 && y < m && !visited[x][y]){
squares.add(new Square(x, y, square.distance + 1);
visited[x][y] = true;
}
}
}

}``````

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

My solution is by doing a BFS and then adjust the steps away from the "G" when popping the stack.

``````public class Quiz_OpenSpaceInMuseum {

public static void main(String args[]) {
// O O O
// O W W
// G O G
//
//   to
//
// 2 3 4
// 1 W W
// G 1 G
String[][] input = new String[][]{
{"O", "O", "O"},
{"O", "W", "W"},
{"G", "O", "G"}};
String[][] output = findOpenSpaceByBrutalForce(input);
System.out.println("Input:");
print(input);
System.out.println("Output:");
print(output);
System.out.println(String.format(Locale.ENGLISH, "%d iteration.\n", mIterationCount));

// O O O O
// O W O G
// O W O O
// O G O O
//
//   to
//
// 4 3 2 1
// 3 W 1 G
// 2 W 2 1
// 1 G 1 2
input = new String[][]{
{"O", "O", "O", "O"},
{"O", "W", "O", "G"},
{"O", "W", "O", "O"},
{"O", "G", "O", "O"}};
output = findOpenSpaceByBrutalForce(input);
System.out.println("Input:");
print(input);
System.out.println("Output:");
print(output);
System.out.println(String.format(Locale.ENGLISH, "%d iteration.\n", mIterationCount));

// O W G O
// O W W O
// O W O O
// O O O G
//
//   to
//
// 6 W G 1
// 5 W W 2
// 4 W 2 1
// 3 2 1 G
input = new String[][]{
{"O", "W", "G", "O"},
{"O", "W", "W", "O"},
{"O", "W", "O", "O"},
{"O", "O", "O", "G"}};
output = findOpenSpaceByBrutalForce(input);
System.out.println("Input:");
print(input);
System.out.println("Output:");
print(output);
System.out.println(String.format(Locale.ENGLISH, "%d iteration.\n", mIterationCount));

// O O G G G
// O W O O O
// O W G W O
// O W W W O
// O O O O O
//
//    to
//
// 2 1 G G G
// 3 W 1 1 1
// 4 W G W 2
// 5 W W W 3
// 6 7 6 5 4
input = new String[][]{
{"O", "O", "G", "G", "G"},
{"O", "W", "O", "O", "O"},
{"O", "W", "G", "W", "O"},
{"O", "W", "W", "W", "O"},
{"O", "O", "O", "O", "O"}};
output = findOpenSpaceByBrutalForce(input);
System.out.println("Input:");
print(input);
System.out.println("Output:");
print(output);
System.out.println(String.format(Locale.ENGLISH, "%d iteration.\n", mIterationCount));
}

///////////////////////////////////////////////////////////////////////////
// Protected / Private Methods ////////////////////////////////////////////

private int mIterationCount = 0;

private static final String OPEN = String.valueOf("O");
private static final String GUARD = String.valueOf("G");

private String[][] findOpenSpaceByBrutalForce(String[][] museum) {
String[][] clone = new String[museum.length][museum.length];
List<Position> guardPosList = new ArrayList<>();

// DEBUG: Init the iteration counter.
mIterationCount = 0;

// Clone the space and find the "G".
// Complexity: O(n^2).
for (int y = 0; y < museum.length; ++y) {
for (int x = 0; x < museum.length; ++x) {
// DEBUG: Accumulate the iteration counter.
++mIterationCount;

clone[y][x] = museum[y][x];

if (museum[y][x].equals(GUARD)) {
}
}
}

// Search from a "G" to another "G".
// Complexity: maximum O(n^2)
for (Position pos : guardPosList) {
// Where the guard is at.
findGuard(clone,
pos.x,
pos.y,
0);
}

return clone;
}

private int findGuard(String[][] museum,
int x,
int y,
int step) {
// Scan if the guard is adjacent. If so, stop the searching.
int right = x + 1 < museum.length ? x + 1 : x;
int left = x - 1 >= 0 ? x - 1 : x;
int bottom = y + 1 < museum.length ? y + 1 : y;
int top = y - 1 >= 0 ? y - 1 : y;
if ((right != x && // right.
museum[y][x + 1].equals(GUARD)) ||
(bottom != y && // bottom.
museum[y + 1][x].equals(GUARD)) ||
(left != x &&  // left.
museum[y][x - 1].equals(GUARD)) ||
(top != y && // top.
museum[y - 1][x].equals(GUARD))) {
// There is a GUARD around, correct the suggested step away from
// the GUARD.
step = 1;
}

if (!museum[y][x].equals(GUARD)) {
museum[y][x] = Integer.toString(step);
}

Stack<Position> todo = new Stack<>();
// Try right one.
if (right != x &&
museum[y][right].equals(OPEN)) {
todo.push(new Position(right, y));
}
// Try bottom one.
if (bottom != y &&
museum[bottom][x].equals(OPEN)) {
todo.push(new Position(x, bottom));
}
// Try left one.
if (left != x &&
museum[y][left].equals(OPEN)) {
todo.push(new Position(left, y));
}
// Try top one.
if (top != y &&
museum[top][x].equals(OPEN)) {
todo.push(new Position(x, top));
}

while (!todo.isEmpty()) {
Position next = todo.pop();

// Compare the returned step with current step.
// If the returned step is less than the current step, it means
// that there is a shorter path and the current step should be
int stepAwayFromGuard = findGuard(museum, next.x, next.y, step + 1);
if (step > stepAwayFromGuard) {
museum[y][x] = Integer.toString(stepAwayFromGuard);
step = stepAwayFromGuard;
}
}

// DEBUG: Accumulate the iteration counter.
++mIterationCount;

return step + 1;
}

private void print(String[][] space) {
for (int y = 0; y < space.length; ++y) {
for (int x = 0; x < space.length; ++x) {
System.out.print(space[y][x]);

if (x < space.length - 1) {
System.out.print("   ");
}
}
System.out.println();
}
}

///////////////////////////////////////////////////////////////////////////
// Clazz //////////////////////////////////////////////////////////////////

private static class Position {
int x;
int y;

public Position(int x, int y) {
this.x = x;
this.y = y;
}

@Override
public boolean equals(Object o) {
if (this == o) return true;
if (o == null || getClass() != o.getClass()) return false;

Position position = (Position) o;

if (x != position.x) return false;
return y == position.y;
}

@Override
public int hashCode() {
int result = x;
result = 31 * result + y;
return result;
}
}
}``````

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

Another Java implementation for the record... BFS...

``````public class MuseumProblem {
static class Node {
int x;
int y;
int distance;
public Node(int x, int y, int distance) {
this.x = x;
this.y = y;
this.distance = distance;
}
public String toString() {
return "["+x+","+y+"]("+distance+")";
}
}

static void calcDistance(int r[][], Node node) {
// double check but needed...
if(node.x < 0 || node.y < 0 || node.x >= r.length || node.y >= r[0].length)
return;
int val = r[node.x][node.y];
if(val == -2) {
// System.out.println("hit a WALL");
return;
}
if(val == 0) {
// System.out.println("hit a Guard");
return;
}
if(val > 0) {
return;
}
r[node.x][node.y] = node.distance+1;
}

static int[][] calculateDistance(char matrix[][]) {
int r[][] = new int[matrix.length][matrix[0].length];

// find Guard and sets the result matrix
// -2: to walls
// -1: to unvisited open space
// 0: to guard
// > 0: distance to Guard
for(int i=0; i < matrix.length; i++) {
for(int j=0; j < matrix[0].length; j++) {
if(matrix[i][j] == 'G') {
r[i][j] = 0;
// distance is -1 to Guard so don't need to check for Guard to +1 to distance...
// Makes the calc simply
}
else if(matrix[i][j] == 'W')
r[i][j] = -2;
else
r[i][j] = -1;
}
}

while(!queue.isEmpty()) {
Node node = queue.poll();

calcDistance(r, node);

// DOWN
int distance = node.distance + 1;
if(node.x+1 < r.length && r[node.x+1][node.y] == -1)
// DOWN LEFT
if(node.x+1 < r.length && node.y-1 >= 0 && r[node.x+1][node.y-1] == -1)
// DOWN RIGHT
if(node.x+1 < r.length && node.y+1 < r[0].length && r[node.x+1][node.y+1] == -1)
// UP
if((node.x-1) >= 0 && r[node.x-1][node.y] == -1)
// UP LEFT
if(node.x-1 >= 0 && node.y-1 >= 0 && r[node.x-1][node.y-1] == -1)
// UP RIGHT
if(node.x-1 >= 0 && node.y+1 < r[0].length && r[node.x-1][node.y+1] == -1)
// LEFT
if((node.y-1) >= 0 && r[node.x][node.y-1] == -1)
// RIGHT
if((node.y+1) < r[0].length && r[node.x][node.y+1] == -1)
}

return r;
}

public static void main(String args[]) {
char[][] matrix = {
{'G','O','O','O','O','O','O','O','O'},
{'W','W','W','W','W','W','W','W','O'},
{'O','O','O','O','O','O','O','O','O'},
{'W','W','W','W','W','O','W','W','W'},
{'O','O','O','O','O','O','O','O','O'},
{'O','W','W','W','W','W','W','W','W'},
{'G','W','O','O','O','O','O','O','O'},
{'O','O','O','W','W','W','W','W','W'}
};

int result[][] = calculateDistance(matrix);
for(int i=0; i < result.length; i++) {
for(int j=0; j < result[0].length; j++) {
if(result[i][j] == -2)
System.out.print("[WW]");
else if(result[i][j]== -1)
System.out.print("[OO]");
else if(result[i][j] == 0) {
System.out.print("[GG]");
}
else
System.out.print(String.format("[%02d]", result[i][j]));
}
System.out.println("");
}
System.out.println("");
}
}``````

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

Calculate distance from each of the 'g' to each of the 'o' (avoiding 'w' and 'g') and store the minimum distance in the result matrix. Update result matrix point if new distance is lower than stored one. Result matrix is initialised with Integer.MAX_VALUE
Below is the working code:

``````import java.util.*;

class Main {
static char[][] matrix = { { 'o', 'o', 'o', 'g', 'o' }, { 'o', 'o', 'w', 'o', 'o' }, { 'o', 'g', 'o', 'o', 'w' },
{ 'o', 'w', 'g', 'o', 'o' }, { 'w', 'o', 'o', 'o', 'g' } };
static  int[][] result =  new int[matrix.length][matrix.length];
public static void main(String[] args) {

for(int i=0;i< matrix.length;i++){
Arrays.fill(result[i],Integer.MAX_VALUE);
}
for(int i=0;i< matrix.length;i++){
for(int j=0;j< matrix.length;j++){
if(matrix[i][j]=='g'){
//calc distances
calcdistances(i,j,0);
}
}
}

//to replace Integer.MAX_VALUE with 'g' and 'w'
String[][] display = new String[matrix.length][matrix.length];
for(int i=0;i< matrix.length;i++){
for(int j=0;j< matrix.length;j++){
if(matrix[i][j]=='g'){
display[i][j]="g";
}else if(matrix[i][j]=='w'){
display[i][j]="w";
}else{
display[i][j]=result[i][j]+"";
}
}
}

for(int i=0;i< display.length;i++){
System.out.println(Arrays.toString(display[i]));
}

}

public static void calcdistances(int r, int c, int currDist){
int cleft = c-1;
if(cleft>=0 && matrix[r][cleft]!='w'&& matrix[r][cleft]!='g') {
if(result[r][cleft]>(currDist+1)){
result[r][cleft] = currDist+1;
calcdistances(r,cleft,result[r][cleft]);
}

}
int cright = c+1;
if(cright<result.length && matrix[r][cright]!='w'&& matrix[r][cright]!='g' ){
if(result[r][cright]>(currDist+1)){
result[r][cright] = currDist+1;
calcdistances(r,cright,result[r][cright]);
}
}

int rtop = r-1;
if(rtop>=0 && matrix[rtop][c]!='w'&& matrix[rtop][c]!='g') {
if(result[rtop][c]>(currDist+1)){
result[rtop][c] = currDist+1;
calcdistances(rtop,c,result[rtop][c]);
}
}
int rbottom = r+1;
if(rbottom<result.length && matrix[rbottom][c]!='w'&& matrix[rbottom][c]!='g') {
if(result[rbottom][c]>(currDist+1)){
result[rbottom][c] = currDist+1;
calcdistances(rbottom,c,result[rbottom][c]);
}
}

}
}``````

Output:

``````[3, 2, 1, g, 1]
[2, 1, w, 1, 2]
[1, g, 1, 2, w]
[2, w, g, 1, 1]
[w, 2, 1, 1, g]``````

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.

### 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.