## Google Interview Question for Software Engineers

Country: United States
Interview Type: Phone Interview

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

``````// Simple BFS
#include <iostream>
#include <queue>
#include <vector>
#include <string>

using namespace std;

const int X = 4;
const int Y = 5;
char const M[X][Y] = {
{'.', '#', '.', 'G', '.'},
{'.', '.', '#', '.', '.'},
{'G', '.', '.', '.', '.'},
{'.', '.', '#', '.', '.'},
};

vector<vector<int>> LEN(
X,
std::vector<int>(Y, X + Y));

struct Vertex
{
int x;
int y;

Vertex(int x, int y): x(x), y(y) { }
};

{
vector<Vertex> a;
if (v.x + 1 < X && M[v.x + 1][v.y] != '#')
a.push_back(Vertex(v.x + 1, v.y));
if (v.x - 1 >= 0 && M[v.x - 1][v.y] != '#')
a.push_back(Vertex(v.x - 1, v.y));
if (v.y + 1 < Y && M[v.x][v.y + 1] != '#')
a.push_back(Vertex(v.x, v.y + 1));
if (v.y - 1 >= 0 && M[v.x][v.y - 1] != '#')
a.push_back(Vertex(v.x, v.y - 1));

return a;
}

void bfs(const Vertex& v)
{
bool visited[X][Y] = { false };
queue<Vertex> q;

q.push(v);
visited[v.x][v.y] = true;

int len = 0;
int levelCount = q.size();

while (q.size())
{
Vertex v = q.front();
q.pop();

if (len < LEN[v.x][v.y])
LEN[v.x][v.y] = len;

for (unsigned i = 0; i != a.size(); ++i)
{
if (!visited[a[i].x][a[i].y])
{
q.push(Vertex(a[i].x, a[i].y));
visited[a[i].x][a[i].y] = true;
}
}

--levelCount;

if (levelCount == 0)
{
++len;
levelCount = q.size();
}
}
}

int main()
{
// Run BFS from each GUARD
for (int i = 0; i != X; ++i)
for (int j = 0; j != Y; ++j)
if (M[i][j] == 'G')
bfs(Vertex(i, j));

// Print the result
for (int i = 0; i != X; ++i)
{
for (int j = 0; j != Y; ++j)
{
if (M[i][j] != 'G' && M[i][j] != '#')
cout << LEN[i][j];
else
cout << M[i][j];
}
cout << endl;
}

}``````

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

I don't think you need to visit edges if (len < LEN[v.x][v.y] is NOT true.
And once you do that, you probably don't need to track visited as well.

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

``````import java.util.Arrays;

public class MuseumGuardian {
static int[] moveX = {0,  0, 1, -1};
static int[] moveY = {1, -1, 0, 0};

public static void main(String[] args) {
char[][] board =
{
{'.', '#', '.', 'G', 'G'},
{'.', '.', '#', '.', '.'},
{'G', '.', '.', '.', '.'},
{'.', '.', '#', '.', '.'}

};

solve(board);
for (char[] arr : board) {
System.out.println(Arrays.toString(arr));
}
}

/// Helper Methods
static int atoi(char c) {
return c - '0';
}

static char itoa(int n) {
return (char)('0' + n);

}

public static void solve(char[][] A) {
for (int i = 0; i < A.length; i++) {
for (int j = 0; j < A[0].length; j++) {
if (A[i][j] == 'G') {
markNeighbors(A, i, j, 0);
}
}
}
}

public static boolean isSafe(char[][] A, int i, int j, int newValue) {
if (i < 0 || i >= A.length || j < 0 || j >= A[0].length) {
return false;
}

if (A[i][j] == 'G' || A[i][j] == '#') {
return false;
}

if (A[i][j] != '.' && atoi(A[i][j]) <= newValue) {
return false;
}

return true;
}

public static void markNeighbors(char[][] A, int i, int j, int value) {
for (int k = 0; k < moveX.length; k++) {
int nextX = i + moveX[k];
int nextY = j + moveY[k];

if (isSafe(A, nextX, nextY, value + 1)) {
A[nextX][nextY] = itoa(value + 1);
markNeighbors(A, nextX, nextY, value + 1);
}
}
}
}``````

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

``````import java.util.Arrays;
public class MuseumGuardian {
static int[] moveX = {0,  0, 1, -1};
static int[] moveY = {1, -1, 0, 0};

public static void main(String[] args) {
char[][] board =
{
{'.', '#', '.', 'G', 'G'},
{'.', '.', '#', '.', '.'},
{'G', '.', '.', '.', '.'},
{'.', '.', '#', '.', '.'}

};

solve(board);
for (char[] arr : board) {
System.out.println(Arrays.toString(arr));
}
}

/// Helper Methods
static int atoi(char c) {
return c - '0';
}

static char itoa(int n) {
return (char)('0' + n);

}

public static void solve(char[][] A) {
for (int i = 0; i < A.length; i++) {
for (int j = 0; j < A[0].length; j++) {
if (A[i][j] == 'G') {
markNeighbors(A, i, j, 0);
}
}
}
}

public static boolean isSafe(char[][] A, int i, int j, int newValue) {
if (i < 0 || i >= A.length || j < 0 || j >= A[0].length) {
return false;
}

if (A[i][j] == 'G' || A[i][j] == '#') {
return false;
}

if (A[i][j] != '.' && atoi(A[i][j]) <= newValue) {
return false;
}

return true;
}

public static void markNeighbors(char[][] A, int i, int j, int value) {
for (int k = 0; k < moveX.length; k++) {
int nextX = i + moveX[k];
int nextY = j + moveY[k];

if (isSafe(A, nextX, nextY, value + 1)) {
A[nextX][nextY] = itoa(value + 1);
markNeighbors(A, nextX, nextY, value + 1);
}
}
}
}``````

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

I don't feel like writing the code for this, but the process is basically to BFS from the guards, and for each empty space, record the depth from the guard in the BFS -> depth of parent + 1. Since we will do multiple BFS's record the minimum depth if it this is possible.

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

@SK I believe that approach should work, so there would be N BFSs for N Guard Cells, each cell would output a Matrix char[][], merge the matrix into one single matrix picking the Min depth of each cell m[i][j], return the resulting merged matrix.

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

exactly.

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

why not we have a global solution matrix and update with the known least value. But in that case we need to somehow track visited locations.

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

``````public static void main(String[] args){
String[][] input = new String[4][5];
input[0][0] = ".";
input[0][1] = "#";
input[0][2] = ".";
input[0][3] = "G";
input[0][4] = ".";

input[1][0] = ".";
input[1][1] = ".";
input[1][2] = "#";
input[1][3] = ".";
input[1][4] = ".";

input[2][0] = "G";
input[2][1] = ".";
input[2][2] = ".";
input[2][3] = ".";
input[2][4] = ".";

input[3][0] = ".";
input[3][1] = ".";
input[3][2] = "#";
input[3][3] = ".";
input[3][4] = ".";

printInput(input);
getDistanceMatrix(input);
printInput(input);
}

static void printInput(String[][] input){
for(int row = 0; row < input.length; row++){
for(int col = 0; col < input[0].length; col++){
System.out.print(input[row][col]);
if(col == input[0].length-1){
System.out.print("\n");
}
}
}
}

static void getDistanceMatrix(String[][] input){
for(int row = 0; row < input.length; row++){
for(int col = 0; col < input[0].length; col++){
if(input[row][col].equals(".")){
input[row][col] = getDistance(input, row, col);
}
}
}
}

static String getDistance(String[][] input, int row, int col){
int MAX = Integer.MAX_VALUE;
int rowDistance = MAX;
int r = row;
//previous row
while(r > 0){
r--;
if(input[r][col].equals("G")){
rowDistance = 1;
break;
}
try{
rowDistance = Integer.parseInt(input[r][col])+1;
break;
}catch(Exception e){

}
}

int guardIdx = -1;
int obstacleNum = 0;
// next row
for(r = row+1; r < input.length; r++){
if(input[r][col].equals("G")){
guardIdx = r;
break;
}
if(input[r][col].equals("#")){
obstacleNum++;
}
}
if(guardIdx > 0){
rowDistance = Math.min(rowDistance, guardIdx-row-obstacleNum);
}

int colDistance = MAX;
int c = col;
//previous col
while(c > 0){
c--;
if(input[row][c].equals("G")){
rowDistance = 1;
break;
}
try{
colDistance = Integer.parseInt(input[row][c])+1;
break;
}catch(Exception e){

}
}

guardIdx = -1;
obstacleNum = 0;
//next Col
for(c = col+1; c < input[0].length; c++){
if(input[row][c].equals("G")){
guardIdx = c;
break;
}
if(input[row][c].equals("#")){
obstacleNum++;
}
}

if(guardIdx > 0){
colDistance = Math.min(colDistance, guardIdx-col-obstacleNum);
}

int distance = Math.min(rowDistance, colDistance);
return String.valueOf(distance);``````

}

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

Doesn't work for all cases. Change the guard position from (2,0) to (2,1) or (2,2) and it gives incorrect distances.

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

@Joe
Thanks for letting me know the error.

I fixed the error.

``````public static void main(String[] args){
//test data
String[][] input = {{".", "#", ".", "G", "."},
{".", ".", "#", ".", "."},
{".", "G", ".", ".", "."},
{".", ".", "#", ".", "."}};

// print the initial matrix
printInput(input);
// get distance matrix
getDistanceMatrix(input);
// print the distance matrix
printInput(input);
}

/**
* print for test
*/
static void printInput(String[][] input){
for(int row = 0; row < input.length; row++){
for(int col = 0; col < input[0].length; col++){
System.out.print(input[row][col]);
if(col == input[0].length-1){
System.out.print("\n");
}
}
}
}

/**
* convert from the initial matrix to the distance matrix
* - each positions of Guard are start point
* @param input
*/
static void getDistanceMatrix(String[][] input){
HashMap<String, Integer> cache = new HashMap<String, Integer>();
for(int row = 0; row < input.length; row++){
for(int col = 0; col < input[0].length; col++){
if(input[row][col].equals("G")){
setDistance(input, row, col, 0, cache);
}
}
}
}

/**
* set the distance value of each position
*
* @param input
* @param row
* @param col
* @param distance
* @param cache
*/
static void setDistance(String[][] input, int row, int col, int distance, HashMap<String, Integer> cache){
if(row < 0 || col < 0 || row >= input.length || col >= input[0].length || input[row][col].equals("#")){
return;
}

String key = row+","+col;
if(cache.containsKey(key) && distance >= cache.get(key)){
return;
}

if(input[row][col].equals(".") || (!input[row][col].equals("#") && !input[row][col].equals("G"))){ // number
distance = getMinDistance(input, row, col, distance);
input[row][col] = String.valueOf(distance);
cache.put(key, Integer.parseInt(input[row][col]));
}else{
cache.put(key, 0);
}
if(!input[row][col].equals("#")){
distance++;
}

setDistance(input, row, col-1, distance, cache);
setDistance(input, row-1, col, distance, cache);
setDistance(input, row, col+1, distance, cache);
setDistance(input, row+1, col, distance, cache);
}

/**
* Find minimum distance from top, bottom, left and right
*
* @param input
* @param row
* @param col
* @param distance
* @return
*/
static int getMinDistance(String[][] input, int row, int col, int distance){
int MAX = Integer.MAX_VALUE;
int top = MAX;
int bottom = MAX;
int left = MAX;
int right = MAX;

//get top value of G
if(row > 0){
int r = row-1;
while(r >= 0){
if(input[r][col].equals("G")){
top = 1;
break;
}else if(input[r][col].equals("#")){
r--;
}else if(input[r][col].equals(".")){
break;
}else{
top = Integer.parseInt(input[r][col])+1;
break;
}
}

if(distance > top){
distance = top;
}
}

// get bottom value of G
if(row < input.length){
int r = row+1;
while(r <= input.length-1){
if(input[r][col].equals("G")){
bottom = 1;
break;
}else if(input[r][col].equals("#")){
r++;
}else if(input[r][col].equals(".")){
break;
}else{
bottom = Integer.parseInt(input[r][col])+1;
break;
}
}

if(distance > bottom){
distance = bottom;
}
}

// get left value of G
if(col > 0){
int c = col-1;
while(c >= 0){
if(input[row][c].equals("G")){
left = 1;
break;
}else if(input[row][c].equals("#")){
c--;
}else if(input[row][c].equals(".")){
break;
}else{
left = Integer.parseInt(input[row][c])+1;
break;
}
}
if(distance > left){
distance = left;
}
}

// get right value of G
if(col < input[0].length){
int c = col+1;
while(c <= input[0].length-1){
if(input[row][c].equals("G")){
right = 1;
break;
}else if(input[row][c].equals("#")){
c++;
}else if(input[row][c].equals(".")){
break;
}else{
right = Integer.parseInt(input[row][c])+1;
break;
}
}
if(distance > right){
distance = right;
}
}
return distance;
}``````

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

@Joe
Thanks.
I fixed the error.

I use recursive method from guard position.

``````public static void main(String[] args){
//test data
String[][] input = {{".", "#", ".", "G", "."},
{".", ".", "#", ".", "."},
{".", "G", ".", ".", "."},
{".", ".", "#", ".", "."}};

// print the initial matrix
printInput(input);
// get distance matrix
getDistanceMatrix(input);
// print the distance matrix
printInput(input);
}

/**
* print for test
*/
static void printInput(String[][] input){
for(int row = 0; row < input.length; row++){
for(int col = 0; col < input[0].length; col++){
System.out.print(input[row][col]);
if(col == input[0].length-1){
System.out.print("\n");
}
}
}
}

/**
* convert from the initial matrix to the distance matrix
* - each positions of Guard are start point
* @param input
*/
static void getDistanceMatrix(String[][] input){
HashMap<String, Integer> cache = new HashMap<String, Integer>();
for(int row = 0; row < input.length; row++){
for(int col = 0; col < input[0].length; col++){
if(input[row][col].equals("G")){
setDistance(input, row, col, 0, cache);
}
}
}
}

/**
* set the distance value of each position
*
* @param input
* @param row
* @param col
* @param distance
* @param cache
*/
static void setDistance(String[][] input, int row, int col, int distance, HashMap<String, Integer> cache){
if(row < 0 || col < 0 || row >= input.length || col >= input[0].length || input[row][col].equals("#")){
return;
}

String key = row+","+col;
if(cache.containsKey(key) && distance >= cache.get(key)){
return;
}

if(input[row][col].equals(".") || (!input[row][col].equals("#") && !input[row][col].equals("G"))){ // number
distance = getMinDistance(input, row, col, distance);
input[row][col] = String.valueOf(distance);
cache.put(key, Integer.parseInt(input[row][col]));
}else{
cache.put(key, 0);
}
if(!input[row][col].equals("#")){
distance++;
}

setDistance(input, row, col-1, distance, cache);
setDistance(input, row-1, col, distance, cache);
setDistance(input, row, col+1, distance, cache);
setDistance(input, row+1, col, distance, cache);
}

/**
* Find minimum distance from top, bottom, left and right
*
* @param input
* @param row
* @param col
* @param distance
* @return
*/
static int getMinDistance(String[][] input, int row, int col, int distance){
int MAX = Integer.MAX_VALUE;
int top = MAX;
int bottom = MAX;
int left = MAX;
int right = MAX;

//get top value of G
if(row > 0){
int r = row-1;
while(r >= 0){
if(input[r][col].equals("G")){
top = 1;
break;
}else if(input[r][col].equals("#")){
r--;
}else if(input[r][col].equals(".")){
break;
}else{
top = Integer.parseInt(input[r][col])+1;
break;
}
}

if(distance > top){
distance = top;
}
}

// get bottom value of G
if(row < input.length){
int r = row+1;
while(r <= input.length-1){
if(input[r][col].equals("G")){
bottom = 1;
break;
}else if(input[r][col].equals("#")){
r++;
}else if(input[r][col].equals(".")){
break;
}else{
bottom = Integer.parseInt(input[r][col])+1;
break;
}
}

if(distance > bottom){
distance = bottom;
}
}

// get left value of G
if(col > 0){
int c = col-1;
while(c >= 0){
if(input[row][c].equals("G")){
left = 1;
break;
}else if(input[row][c].equals("#")){
c--;
}else if(input[row][c].equals(".")){
break;
}else{
left = Integer.parseInt(input[row][c])+1;
break;
}
}
if(distance > left){
distance = left;
}
}

// get right value of G
if(col < input[0].length){
int c = col+1;
while(c <= input[0].length-1){
if(input[row][c].equals("G")){
right = 1;
break;
}else if(input[row][c].equals("#")){
c++;
}else if(input[row][c].equals(".")){
break;
}else{
right = Integer.parseInt(input[row][c])+1;
break;
}
}
if(distance > right){
distance = right;
}
}
return distance;
}``````

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

``````void findGuardDistances(Museum museum) {
for (int x = 0; x < museum.width(); x++) {
for (int y = 0; y < museum.height(); y++) {
if (museum.cellAt(x, y) instanceof Guard) {
}
}
}
while (!queue.isEmpty()) {
Record record = queue.poll();
int nextDistance = record.distance() + 1;
for (Neighbour n : Neighbour.values()) {
int nx = record.x() + n.dx();
int ny = record.y() + n.dy();
if (museum.cellAt(nx, ny) instanceof EmptySpace) {
museum.set(nx, ny, new GuardDistance(nextDistance));
}
}
}
}``````

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

I decided to receive the input as an array of open space nodes.

{{
def update_guard_distances(open_space_nodes):
for open_space_node in open_space_nodes:
open_space_node.get_distance_to_guard()

MAX = 10000000

class Node():
def __init__(self, label, neighbors, connected_to_guard=False, dist_to_guard=None):
self.label = label
self.open_neighbors = neighbors
self.connected_directly_to_guard = connected_to_guard
self.distance_to_guard = dist_to_guard

def get_distance_to_guard(self):
# base case
if self.connected_directly_to_guard:
self.distance_to_guard = 1

# recursive case / need to populate
elif not self.distance_to_guard:
closest_distance_to_guard = MAX
for neighbor in self.open_neighbors:
closest_distance_to_guard = min(closest_distance_to_guard, 1 + neighbor.get_distance_to_guard())
self.distance_to_guard = closest_distance_to_guard
# has been populated
return self.distance_to_guard

a = Node('a', [])
b = Node('b', [])
c = Node('c', [])
d = Node('d', [], True)
a.open_neighbors.append(d)
e = Node('e', [d])
d.open_neighbors.append(a)
d.open_neighbors.append(e)

nodes = [a, b, c, d, e]
update_guard_distances(nodes)
for node in nodes:
if node.distance_to_guard:
print(node.distance_to_guard)
}}

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

I decided to receive the input as an array of open space nodes.

{{
def update_guard_distances(open_space_nodes):
for open_space_node in open_space_nodes:
open_space_node.get_distance_to_guard()

MAX = 10000000

class Node():
def __init__(self, label, neighbors, connected_to_guard=False, dist_to_guard=None):
self.label = label
self.open_neighbors = neighbors
self.connected_directly_to_guard = connected_to_guard
self.distance_to_guard = dist_to_guard

def get_distance_to_guard(self):
# base case
if self.connected_directly_to_guard:
self.distance_to_guard = 1

# recursive case / need to populate
elif not self.distance_to_guard:
closest_distance_to_guard = MAX
for neighbor in self.open_neighbors:
closest_distance_to_guard = min(closest_distance_to_guard, 1 + neighbor.get_distance_to_guard())
self.distance_to_guard = closest_distance_to_guard
# has been populated
return self.distance_to_guard

a = Node('a', [])
b = Node('b', [])
c = Node('c', [])
d = Node('d', [], True)
a.open_neighbors.append(d)
e = Node('e', [d])
d.open_neighbors.append(a)
d.open_neighbors.append(e)

nodes = [a, b, c, d, e]
update_guard_distances(nodes)
for node in nodes:
if node.distance_to_guard:
print(node.distance_to_guard)
}}

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

I decided to receive the input as an array of open space nodes.

``````def update_guard_distances(open_space_nodes):
for open_space_node in open_space_nodes:
open_space_node.get_distance_to_guard()

MAX = 10000000

class Node():
def __init__(self, label, neighbors, connected_to_guard=False, dist_to_guard=None):
self.label = label
self.open_neighbors = neighbors
self.connected_directly_to_guard = connected_to_guard
self.distance_to_guard = dist_to_guard

def get_distance_to_guard(self):
# base case
if self.connected_directly_to_guard:
self.distance_to_guard = 1

# recursive case / need to populate
elif not self.distance_to_guard:
closest_distance_to_guard = MAX
for neighbor in self.open_neighbors:
closest_distance_to_guard = min(closest_distance_to_guard, 1 + neighbor.get_distance_to_guard())
self.distance_to_guard = closest_distance_to_guard
# has been populated
return self.distance_to_guard

a = Node('a', [])
b = Node('b', [])
c = Node('c', [])
d = Node('d', [], True)
a.open_neighbors.append(d)
e = Node('e', [d])
d.open_neighbors.append(a)
d.open_neighbors.append(e)

nodes = [a, b, c, d, e]
update_guard_distances(nodes)
for node in nodes:
if node.distance_to_guard:
print(node.distance_to_guard)``````

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

dynamic programming anyone ? wake up people

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

// Simple BFS

#include <iostream>
#include <queue>
#include <vector>
#include <string>

using namespace std;

const int X = 4;
const int Y = 5;
char const M[X][Y] = {
{'.', '#', '.', 'G', '.'},
{'.', '.', '#', '.', '.'},
{'G', '.', '.', '.', '.'},
{'.', '.', '#', '.', '.'},
};

vector<vector<int>> LEN(
X,
std::vector<int>(Y, X + Y));

struct Vertex
{
int x;
int y;

Vertex(int x, int y): x(x), y(y) { }
};

{
vector<Vertex> a;
if (v.x + 1 < X && M[v.x + 1][v.y] != '#')
a.push_back(Vertex(v.x + 1, v.y));
if (v.x - 1 >= 0 && M[v.x - 1][v.y] != '#')
a.push_back(Vertex(v.x - 1, v.y));
if (v.y + 1 < Y && M[v.x][v.y + 1] != '#')
a.push_back(Vertex(v.x, v.y + 1));
if (v.y - 1 >= 0 && M[v.x][v.y - 1] != '#')
a.push_back(Vertex(v.x, v.y - 1));

return a;
}

void bfs(const Vertex& v)
{
bool visited[X][Y] = { false };
queue<Vertex> q;

q.push(v);
visited[v.x][v.y] = true;

int len = 0;
int levelCount = q.size();

while (q.size())
{
Vertex v = q.front();
q.pop();

if (len < LEN[v.x][v.y])
LEN[v.x][v.y] = len;

for (unsigned i = 0; i != a.size(); ++i)
{
if (!visited[a[i].x][a[i].y])
{
q.push(Vertex(a[i].x, a[i].y));
visited[a[i].x][a[i].y] = true;
}
}

--levelCount;

if (levelCount == 0)
{
++len;
levelCount = q.size();
}
}
}

int main()
{
// Run BFS from each GUARD
for (int i = 0; i != X; ++i)
for (int j = 0; j != Y; ++j)
if (M[i][j] == 'G')
bfs(Vertex(i, j));

// Print the result
for (int i = 0; i != X; ++i)
{
for (int j = 0; j != Y; ++j)
{
if (M[i][j] != 'G' && M[i][j] != '#')
cout << LEN[i][j];
else
cout << M[i][j];
}
cout << endl;
}

}

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

// Simple BFS

#include <iostream>
#include <queue>
#include <vector>
#include <string>

using namespace std;

const int X = 4;
const int Y = 5;
char const M[X][Y] = {
{'.', '#', '.', 'G', '.'},
{'.', '.', '#', '.', '.'},
{'G', '.', '.', '.', '.'},
{'.', '.', '#', '.', '.'},
};

vector<vector<int>> LEN(
X,
std::vector<int>(Y, X + Y));

struct Vertex
{
int x;
int y;

Vertex(int x, int y): x(x), y(y) { }
};

{
vector<Vertex> a;
if (v.x + 1 < X && M[v.x + 1][v.y] != '#')
a.push_back(Vertex(v.x + 1, v.y));
if (v.x - 1 >= 0 && M[v.x - 1][v.y] != '#')
a.push_back(Vertex(v.x - 1, v.y));
if (v.y + 1 < Y && M[v.x][v.y + 1] != '#')
a.push_back(Vertex(v.x, v.y + 1));
if (v.y - 1 >= 0 && M[v.x][v.y - 1] != '#')
a.push_back(Vertex(v.x, v.y - 1));

return a;
}

void bfs(const Vertex& v)
{
bool visited[X][Y] = { false };
queue<Vertex> q;

q.push(v);
visited[v.x][v.y] = true;

int len = 0;
int levelCount = q.size();

while (q.size())
{
Vertex v = q.front();
q.pop();

if (len < LEN[v.x][v.y])
LEN[v.x][v.y] = len;

for (unsigned i = 0; i != a.size(); ++i)
{
if (!visited[a[i].x][a[i].y])
{
q.push(Vertex(a[i].x, a[i].y));
visited[a[i].x][a[i].y] = true;
}
}

--levelCount;

if (levelCount == 0)
{
++len;
levelCount = q.size();
}
}
}

int main()
{
// Run BFS from each GUARD
for (int i = 0; i != X; ++i)
for (int j = 0; j != Y; ++j)
if (M[i][j] == 'G')
bfs(Vertex(i, j));

// Print the result
for (int i = 0; i != X; ++i)
{
for (int j = 0; j != Y; ++j)
{
if (M[i][j] != 'G' && M[i][j] != '#')
cout << LEN[i][j];
else
cout << M[i][j];
}
cout << endl;
}

}

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

``````// Simple BFS
#include <iostream>
#include <queue>
#include <vector>
#include <string>

using namespace std;

const int X = 4;
const int Y = 5;
char const M[X][Y] = {
{'.', '#', '.', 'G', '.'},
{'.', '.', '#', '.', '.'},
{'G', '.', '.', '.', '.'},
{'.', '.', '#', '.', '.'},
};

vector<vector<int>> LEN(
X,
std::vector<int>(Y, X + Y));

struct Vertex
{
int x;
int y;

Vertex(int x, int y): x(x), y(y) { }
};

{
vector<Vertex> a;
if (v.x + 1 < X && M[v.x + 1][v.y] != '#')
a.push_back(Vertex(v.x + 1, v.y));
if (v.x - 1 >= 0 && M[v.x - 1][v.y] != '#')
a.push_back(Vertex(v.x - 1, v.y));
if (v.y + 1 < Y && M[v.x][v.y + 1] != '#')
a.push_back(Vertex(v.x, v.y + 1));
if (v.y - 1 >= 0 && M[v.x][v.y - 1] != '#')
a.push_back(Vertex(v.x, v.y - 1));

return a;
}

void bfs(const Vertex& v)
{
bool visited[X][Y] = { false };
queue<Vertex> q;

q.push(v);
visited[v.x][v.y] = true;

int len = 0;
int levelCount = q.size();

while (q.size())
{
Vertex v = q.front();
q.pop();

if (len < LEN[v.x][v.y])
LEN[v.x][v.y] = len;

for (unsigned i = 0; i != a.size(); ++i)
{
if (!visited[a[i].x][a[i].y])
{
q.push(Vertex(a[i].x, a[i].y));
visited[a[i].x][a[i].y] = true;
}
}

--levelCount;

if (levelCount == 0)
{
++len;
levelCount = q.size();
}
}
}

int main()
{
// Run BFS from each GUARD
for (int i = 0; i != X; ++i)
for (int j = 0; j != Y; ++j)
if (M[i][j] == 'G')
bfs(Vertex(i, j));

// Print the result
for (int i = 0; i != X; ++i)
{
for (int j = 0; j != Y; ++j)
{
if (M[i][j] != 'G' && M[i][j] != '#')
cout << LEN[i][j];
else
cout << M[i][j];
}
cout << endl;
}

}``````

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

``````const int X = 4;
const int Y = 5;
char const M[X][Y] = {
{'.', '#', '.', 'G', '.'},
{'.', '.', '#', '.', '.'},
{'G', '.', '.', '.', '.'},
{'.', '.', '#', '.', '.'},
};

vector<vector<int>> LEN(
X,
std::vector<int>(Y, X + Y));

struct Vertex
{
int x;
int y;

Vertex(int x, int y): x(x), y(y) { }
};

{
vector<Vertex> a;
if (v.x + 1 < X && M[v.x + 1][v.y] != '#')
a.push_back(Vertex(v.x + 1, v.y));
if (v.x - 1 >= 0 && M[v.x - 1][v.y] != '#')
a.push_back(Vertex(v.x - 1, v.y));
if (v.y + 1 < Y && M[v.x][v.y + 1] != '#')
a.push_back(Vertex(v.x, v.y + 1));
if (v.y - 1 >= 0 && M[v.x][v.y - 1] != '#')
a.push_back(Vertex(v.x, v.y - 1));

return a;
}

void bfs(const Vertex& v)
{
bool visited[X][Y] = { false };
queue<Vertex> q;

q.push(v);
visited[v.x][v.y] = true;

int len = 0;
int levelCount = q.size();

while (q.size())
{
Vertex v = q.front();
q.pop();

if (len < LEN[v.x][v.y])
LEN[v.x][v.y] = len;

for (unsigned i = 0; i != a.size(); ++i)
{
if (!visited[a[i].x][a[i].y])
{
q.push(Vertex(a[i].x, a[i].y));
visited[a[i].x][a[i].y] = true;
}
}

--levelCount;

if (levelCount == 0)
{
++len;
levelCount = q.size();
}
}
}

int main()
{
// Run BFS from each GUARD
for (int i = 0; i != X; ++i)
for (int j = 0; j != Y; ++j)
if (M[i][j] == 'G')
bfs(Vertex(i, j));

// Print the result
for (int i = 0; i != X; ++i)
{
for (int j = 0; j != Y; ++j)
{
if (M[i][j] != 'G' && M[i][j] != '#')
cout << LEN[i][j];
else
cout << M[i][j];
}
cout << endl;
}
}``````

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

``````const int X = 4;
const int Y = 5;
char const M[X][Y] = {
{'.', '#', '.', 'G', '.'},
{'.', '.', '#', '.', '.'},
{'G', '.', '.', '.', '.'},
{'.', '.', '#', '.', '.'},
};

vector<vector<int>> LEN(
X,
std::vector<int>(Y, X + Y));

struct Vertex
{
int x;
int y;

Vertex(int x, int y): x(x), y(y) { }
};

{
vector<Vertex> a;
if (v.x + 1 < X && M[v.x + 1][v.y] != '#')
a.push_back(Vertex(v.x + 1, v.y));
if (v.x - 1 >= 0 && M[v.x - 1][v.y] != '#')
a.push_back(Vertex(v.x - 1, v.y));
if (v.y + 1 < Y && M[v.x][v.y + 1] != '#')
a.push_back(Vertex(v.x, v.y + 1));
if (v.y - 1 >= 0 && M[v.x][v.y - 1] != '#')
a.push_back(Vertex(v.x, v.y - 1));

return a;
}

void bfs(const Vertex& v)
{
bool visited[X][Y] = { false };
queue<Vertex> q;

q.push(v);
visited[v.x][v.y] = true;

int len = 0;
int levelCount = q.size();

while (q.size())
{
Vertex v = q.front();
q.pop();

if (len < LEN[v.x][v.y])
LEN[v.x][v.y] = len;

for (unsigned i = 0; i != a.size(); ++i)
{
if (!visited[a[i].x][a[i].y])
{
q.push(Vertex(a[i].x, a[i].y));
visited[a[i].x][a[i].y] = true;
}
}

--levelCount;

if (levelCount == 0)
{
++len;
levelCount = q.size();
}
}
}

int main()
{
// Run BFS from each GUARD
for (int i = 0; i != X; ++i)
for (int j = 0; j != Y; ++j)
if (M[i][j] == 'G')
bfs(Vertex(i, j));

// Print the result
for (int i = 0; i != X; ++i)
{
for (int j = 0; j != Y; ++j)
{
if (M[i][j] != 'G' && M[i][j] != '#')
cout << LEN[i][j];
else
cout << M[i][j];
}
cout << endl;
}
}``````

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

It is a great question. In order to solve it, we have to make a Breath First Search from every guard until we reach every floor cell in the maze then we can merge the matrix of every guard by taking the minimum distance. This is my complete implementation with the expected output.

``````import java.util.ArrayList;
import java.util.List;
import java.util.Queue;

public class MazeScanner {
public static char[][] space = {
{'.', '#', '.', 'G', '.' },
{'.', '.', '#', '.', '.' },
{'G', '.', '.', '.', '.' },
{'.', '.', '#', '.', '.' },
};

static class Position {
int x;
int y;

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

@Override
public boolean equals(Object obj) {
if (!(obj instanceof Position)) {
return false;
}

Position pos = (Position) obj;

if (this.x == pos.x && this.y == pos.y) {
return true;
}

return false;
}

@Override
public String toString() {
return "(" + x + ", " + y + ")";
}
}

public static Integer[][] solveMaze(char[][] space, Position guard) {
Integer[][] output = new Integer[space.length][space[0].length];
List<Position> visited = new ArrayList<>();

for (int i = 0; i < output.length; ++i) {
for (int j = 0; j < output[0].length; ++j) {
output[i][j] = -1;
}
}

output[guard.x][guard.y] = 0;

while (! queue.isEmpty()) {
Position position = queue.poll();

if (output[position.x][position.y] == -1) {
Integer value = getNearestValue(output, position.x, position.y);

output[position.x][position.y] = value + 1;
}

List<Position> positions = getPossibleNeighours(space, position, visited);

if (positions.size() >= 1) {
}
}

return output;
}

public static String[][] solveMaze(char[][] space, Position[] guards) {
Integer[][] output = new Integer[space.length][space[0].length];
List<Integer[][]> possibleSolutions = new ArrayList<>();

for (int i = 0; i < guards.length; ++i) {
Integer[][] out = solveMaze(space, guards[i]);

//print2DArray(out);

}

for (int i = 0; i < output.length; ++i) {
for (int j = 0; j < output[0].length; ++j) {
int minimumPositive = Integer.MAX_VALUE;

for (int z = 0; z < possibleSolutions.size(); ++z) {
if (possibleSolutions.get(z)[i][j] < minimumPositive && possibleSolutions.get(z)[i][j] > 0) {
minimumPositive = possibleSolutions.get(z)[i][j];
}
}

if (minimumPositive != Integer.MAX_VALUE) {
output[i][j] = minimumPositive;
} else {
output[i][j] = -1;
}
}
}

String[][] finalOutput = new String[space.length][space[0].length];

for (int i = 0; i < finalOutput.length; ++i) {
for (int j = 0; j < finalOutput[0].length; ++j) {
if (output[i][j] > 0 && space[i][j] != 'G' && space[i][j] != '#') {
finalOutput[i][j] = output[i][j] + "";
} else {
finalOutput[i][j] = space[i][j] + "";
}
}
}

return finalOutput;
}

private static Integer getNearestValue(Integer[][] output, Integer x, Integer y) {
if (x + 1 <= output.length - 1 && output[x + 1][y] != -1) {
return output[x + 1][y];
}

if (x - 1 >= 0 && output[x - 1][y] != -1) {
return output[x - 1][y];
}

if (y + 1 <= output[0].length - 1 && output[x][y + 1] != -1) {
return output[x][y + 1];
}

if (y - 1 >= 0 && output[x][y - 1] != -1) {
return output[x][y - 1];
}

throw new RuntimeException("[Severe] cannot get a nearest value ...");
}

private static List<Position> getPossibleNeighours(char[][] space, Position position, List<Position> visited) {
int x = position.x;
int y = position.y;

List<Position> positions = new ArrayList<>();

if (x + 1 <= space.length - 1 && space[x + 1][y] != '#' && space[x + 1][y] != 'G') {
Position pos = new Position(x + 1, y);

if (! visited.contains(pos)) {
}
}

if (x - 1 >= 0 && space[x - 1][y] != -1 && space[x - 1][y] != '#' && space[x - 1][y] != 'G') {
Position pos = new Position(x - 1, y);

if (! visited.contains(pos)) {
}
}

if (y + 1 <= space[0].length - 1 && space[x][y + 1] != -1 && space[x][y + 1] != '#' && space[x][y + 1] != 'G') {
Position pos = new Position(x, y + 1);

if (! visited.contains(pos)) {
}
}

if (y - 1 >= 0 && space[x][y - 1] != -1 && space[x][y - 1] != '#' && space[x][y - 1] != 'G') {
Position pos = new Position(x, y - 1);

if (! visited.contains(pos)) {
}
}

return positions;
}

public static void main(String[] args) {
Position[] positions = new Position[] {
new Position(2, 0),
new Position(0, 3)
};

String[][] output = solveMaze(space, positions);

print2DArray(output);
}

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

}``````

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

i think we can save ourself from doing BFS on N nodes. Here is what i propose:-
(1) first traverse the whole array and while traversing whenever you find a G, we turn all the accessible points from that G with distance of 1 only as 1, i.e. the immediate n, s, e, w points to this G as 1. and keep putting these cells in a queue.
(2) while the queue is not empty, we pop one element (one cell) and turn it's n, s, e, w to be min(it's neighbors + 1); and put this new cell in queue.
NOTE: since not all the neighbors are having the value we just take those that have and we shall check this value again. Also the cells that have value as 1 cannot be better than that so we don't enqueue them again.

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

Madhur, I replied to your comment but it appears as separate answer, please find my comment which starts with "This is the answer I wrote in my interview. This algorithm works..."

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

I was looking at this question for long time waiting for a good answer to come! (I posted this question). The best algorithm for this problem is of O(nlogn). it gets implemented using shortest path algorithm (Dijkstra). The famous algorithm should be modified slightly as follows:
1. in the beginning, all of the guard locations can be starting point. Therefore, instead of just adding one point to the main heap in the code, we add all of the guard locations to that heap with distance of 0.
2. Instead of ending the algorithm when destination is met, the algorithm ends when the main heap is empty, meaning all of the locations are met.
With these modifications, Dijkstra algorithm with O(nlogn) can solve it.

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

Hi when you say a Dijkstra's algorithm, how would you do that since it is possible only in a directed graph and this is not.... because if we are able to go from arr[i][j] to arr[i-1][j] then reverse is also true... Please correct me if I am wrong. Moreover when you say you would use HEAP DS then do you intend to change the structure of Heap DS as a node can have 2 children but in this question a node can have 4 immediate children (n, s, e, w);

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

This is the answer I wrote in my interview. This algorithm works for many cases but it is wrong. It can produce wrong results. The logic to explain why it is wrong is very complex and unfortunately I don't have time to explain it. One of my Googler friends told me why it was wrong. Even the interviewer told me I solved it right and he did not realize the logic error while I was writing the code.

Anyways I write the code I gave in my interview here. FYI, I didn't get the offer. So this code is not good enough eventhough it works for many cases.

``````class Pairs {

int MAXCOL = 1000;
private int row;
private int col;

pubic Pairs(int r, int c) {
row = r;
col = c;
}

public int getRow() {
return row;
}

public int getCol() {
return col;
}

public boolean isEqual(Pairs p) {
return (this.row == p.row && this.col == p.row);
}

public int hashCode() {
return row * MAXCOL + col;
}

}

class Museum {

List<Pairs> obstacles;
List<Pairs> guards;
int rowSize;
int colSize;

public Museum(List<Pairs> o, List<Pairs> g, int row, int col) {

obstacles = o;
guards = g;
rowSize = row;
colSize = col;
//There should be checking that all the pairs inside o and g are within map
//...
}

public Map<Pairs, Integer> getGuardDistance() {

//First create a queue of all the empty spaces
Map<Pairs, Integer> distances = new HashMap<>();
for (int i = 0; i < rowSize; i++) {
for (int j = 0; j < colSize; j++) {
Pairs p = new Pairs(i, j);
if ((!obstacles.contains(p)) && (!guards.contains(p))) {
distances.put(p, Integer.MAX_VALUE);
}
if (guards.contains(p)) {
distances.put(p, 0);
}
if (obstacles.contains(p)) {
distances.put(p, Integer.MAX_VALUE);
}
}
}
//as long as I have something in the que
while (!notFilinzed.isEmpty()) {
Pair p = notFilinzed.poll();
int min = Integer.MAX_VALUE;
boolean foundDistance = false;
//top:
if (p.row - 1 >= 0) {
Pairs top = new Pairs(p.row - 1, p.col);
if (!notFilinzed.contains(top) && !obstacles.contains(top) && distances.get(top) < min) {
min = distances.get(top);
foundDistance = true;
}
}
//right
if (p.col + 1 < colSize) {
Pairs right = new Pairs(p.row, p.col + 1);
if (!notFilinzed.contains(right) && !obstacles.contains(right) && distances.get(right) < min) {
min = distances.get(right);
foundDistance = true;
}
}
//bottom
if (p.row < rowSize) {
Pairs bottom = new Pairs(p.row + 1, p.col);
if (!notFilinzed.contains(bottom) && !obstacles.contains(bottom) && distances.get(bottom) < min) {
min = distances.get(bottom);
foundDistance = true;
}
}
//left
if (p.col - 1 >= 0) {
Pairs left = new Pairs(p.row, p.col - 1);
if (!notFilinzed.contains(left) && !obstacles.contains(left) && distances.get(left) < min) {
min = distances.get(left);
foundDistance = true;
}
}
if (!foundDistance) {
}
distances.put(p, min + 1);
}

//Create output format
return distances;
}

}``````

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

Hello amirtar,
This is the code that i wrote. It has a slight modification of saving the best path once i reach a guard and the path i took to reach that guard. This way i save myself from doing a BFS on all nodes.

``````package arrays;

import java.util.HashSet;
import java.util.Queue;
import java.util.Set;

public class GuardEmptySpace {

/*char[][] museum = {
{'.', '#', '.', 'G', '.'},
{'.', '.', '#', '.', '.'},
{'G', '.', '.', '.', '.'},
{'.', '.', '#', '.', '.'}
};*/

char[][] museum = {
{'.', '.', '.', 'G'},
{'.', '.', '.', '.'},
{'G', '#', '#', '.'},
{'.', 'G', '#', '.'}
};
int[][] space = new int[museum.length][museum[0].length];

Queue<String> q;
Set<String> set;

public static void main(String[] args) {
GuardEmptySpace ges = new GuardEmptySpace();
ges.findSpace();
}

private void findSpace() {
for (int i = 0; i < museum.length; i++) {
for (int j = 0; j < museum[0].length; j++) {
if (museum[i][j] == 'G') {
//set n, s, e, w to be accessible in just one unit of space if they are not having #
setSpace(i, j);
space[i][j] = Integer.MIN_VALUE;
} else if (museum[i][j] == '#') {
space[i][j] = Integer.MAX_VALUE;
}
}
}
for (int i = 0; i < museum.length; i++) {
for (int j = 0; j < museum[0].length; j++) {
set = new HashSet<String>();
if (space[i][j] == 0) {
setPath(performBFS());
}
}
}

for (int i = 0; i < museum.length; i++) {
for (int j = 0; j < museum[0].length; j++) {
if (space[i][j] == Integer.MIN_VALUE) {
System.out.print("G");
} else if (space[i][j] == Integer.MAX_VALUE) {
System.out.print("#");
} else {
System.out.print(space[i][j]);
}
}
System.out.println();
}
}

private void setPath(String s) {
String[] split = s.split(";");
int k = 1;
for (int i = split.length - 2; i >= 0; i--, k++) {
String[] split2 = split[i].split(",");
space[Integer.parseInt(split2[0])][Integer.parseInt(split2[1])] = k;
}
}

private String performBFS() {
int i, j;
while (!q.isEmpty()) {
StringBuilder sb = new StringBuilder(q.poll());
String str = getIndexString(sb.toString());
String[] split = str.split(",");
i = Integer.parseInt(split[0]);
j = Integer.parseInt(split[1]);
if (museum[i][j] == 'G') {
return sb.toString();
} else {
changeQueue(sb.toString(), i - 1, j);
changeQueue(sb.toString(), i + 1, j);
changeQueue(sb.toString(), i, j - 1);
changeQueue(sb.toString(), i, j + 1);
}
}
return "";
}

private void changeQueue(String str, int i, int j) {
StringBuilder sb = new StringBuilder(str);
if (isGoodCell(i, j)) {
}
}

private String getIndexString(String str) {
String[] split = str.split(";");
int size = split.length;
return split[size - 1];
}

private boolean isGoodCell(int i, int j) {
if ((i < museum.length && i >= 0) && (j < museum[0].length && j >= 0)) {
if ((!set.contains(i + "," + j)) && (space[i][j] != Integer.MAX_VALUE)) {
return true;
}
}
return false;
}

private void setSpace(int i, int j) {
// set north
if ((i - 1 >= 0) && (space[i - 1][j] != '#')) {
space[i - 1][j] = 1;
}
// set south
if ((i + 1 < museum.length) && (space[i + 1][j] != '#')) {
space[i + 1][j] = 1;
}
//set east
if ((j - 1 >= 0) && (space[i][j - 1] != '#')) {
space[i][j - 1] = 1;
}
if ((j + 1 < museum[0].length) && (space[i][j + 1] != '#')) {
space[i][j + 1] = 1;
}
}
}``````

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

Hello Madhur, your code does not seem to have the error I thought. I tested a couple of cases I thought may produce bug, but it didn't. Unfortunately, I could not read your code. I think you need to use data structures rather than passing i and j as string and then parsing them back to integer. This does not seem like a good policy if you are doing job interview and makes the code harder to read.

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

This question is a simple modification of dijkstra. i.e with multiple sources. Complexity would be the same as v^2, that is in this case (n*m)^2.

``````struct node
{
int val;
int i;
int j;
node(int val_, int l_, int r_) :val(val_), i(l_), j(r_){}
};

class comparator
{
public:
bool operator() (node n1, node n2)
{
return n1.val > n2.val;
}
};

void fillmap(int n, int m, char arry[6][5])
{
priority_queue<node, vector<node>, comparator> pq;
for (int i = 0; i < n; ++i)
{
for (int j = 0; j < m; ++j)
{
if (arry[i][j] == 'G')arry[i][j] = 0;
//if (arry[i][j] == '#')arry[i][j] = CHAR_MAX;
if (arry[i][j] == '.')arry[i][j] = CHAR_MAX;
}
}
for (int i = 0; i < n; ++i)
{
for (int j = 0; j < m; ++j)
{
if (arry[i][j] == 0)pq.push(node(0, i, j));
}
}
while (!pq.empty())
{
node nd = pq.top();
pq.pop();
if (nd.i - 1 >= 0 && arry[nd.i - 1][nd.j] != '#' && arry[nd.i - 1][nd.j] > arry[nd.i][nd.j] + 1)
{
arry[nd.i - 1][nd.j] = arry[nd.i][nd.j] + 1;
pq.push(node(arry[nd.i][nd.j] + 1, nd.i - 1, nd.j));
}
if (nd.i + 1 != n && arry[nd.i + 1][nd.j] != '#' && arry[nd.i + 1][nd.j] > arry[nd.i][nd.j] + 1)
{
arry[nd.i + 1][nd.j] = arry[nd.i][nd.j] + 1;
pq.push(node(arry[nd.i][nd.j] + 1, nd.i + 1, nd.j));
}
if (nd.j - 1 >= 0 && arry[nd.i][nd.j - 1] != '#' && arry[nd.i][nd.j - 1] > arry[nd.i][nd.j] + 1)
{
arry[nd.i][nd.j - 1] = arry[nd.i][nd.j] + 1;
pq.push(node(arry[nd.i][nd.j] + 1, nd.i, nd.j - 1));
}
if (nd.j + 1 != m && arry[nd.i][nd.j + 1] != '#' && arry[nd.i][nd.j + 1] > arry[nd.i][nd.j] + 1)
{
arry[nd.i][nd.j + 1] = arry[nd.i][nd.j] + 1;
pq.push(node(arry[nd.i][nd.j] + 1, nd.i, nd.j + 1));
}
}
for (int i = 0; i < n; ++i)
{
for (int j = 0; j < m; ++j)
{
cout << (int)arry[i][j] << " ";
}
cout << endl;
}
}``````

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

My general idea takes principles from Dijkstra's algorithm and backtracking.
We essentially backtrack from all guards, setting distances of surrounding free cells to 1.
Whenever a distance gets 'relaxed' (see Dijkstra), update distances of surrounding free cells if they would be reduced. This cascading effect will continue for each guard until no cells can be relaxed any further. At this point, you end up with the min distances for each empty space to some guard.

Ex:
- Create 2D array R to hold results, initially setting all distances to infinity
- For each location L in input matrix M
If M[L] is 'G', for each direction D (up/down/left/right), if M[D] is '.' and R[D] > 1, R[D] = 1 and recurse on D
If M[L] is '.', for each direction D, if M[D] is '.' and R[D] > R[L] + 1, R[D] = R[L] + 1 and recurse on D

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

Keep the data in a 2d array of ints where it can be a pseudo graph. Then complete a DFS from each position to the Guard using previous computations to short circuit the computations.

``````public static final int WALL=Integer.MAX_VALUE;
public static final int UNCHECKED = -2;
public static final int OPEN = -1;
public static final int GUARD = 0;

public static void computeDistance(int[][] room){
class Worker{
int[][] area;
int[][] results;

private Worker(int[][] area, int[][] results){
this.area = area;
this.results = new int[area.length][area[0].length];
for(int y = 0; y < this.area.length; y++){
for(int x = 0; x < this.area[0].length; x++){
this.results[y][x] =UNCHECKED;
}
}
}

private void work(){
for(int y = 0; y < this.area.length; y++){
for(int x = 0; x < this.area[0].length; x++){
this.work(x, y);
}
}
}

private int work(int x, int y){
if(y < 0 || y > this.area.length){
return WALL;
}
if(x < 0 || x > this.area[0].length){
return WALL;
}
int returnVal = this.results[y][x];
if(returnVal != UNCHECKED){
return returnVal ;
}
int areaVal = this.area[y][x];
if(areaVal == WALL){
returnVal = WALL;
}
else if(areaVal == GUARD){
returnVal = GUARD;
}
else if(areaVal == OPEN){
returnVal  = Math.min(work(x, y+1), Math.min(x+1, y, Math.min(work(x, y-1), work(x-1, y))));
if(returnVal == WALL){
returnVal = OPEN;
}
else if(returnVal < WALL && returnVal > OPEN){
returnVal++;
}
}
this.results[y][x] = returnVal;
return returnVal;
}
}
Worker worker = new Worker(room);
worker.work();
return worker.results;
}``````

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

``````public class HelloWorld{

public static void main(String []args){
char input[][]= {{'.','#','.','G','.'}, {'.','.','#','.','.'}, {'G','.','.','.','.'}, {'.','.','#','.','.'}} ;

char[][] result= f(input);
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 static char[][] f(char[][] arr){
int m= arr.length;
int n= arr[0].length;
char[][] buff= new char[m][n];
int[][] A= new int[m][n];
int tcount=0; // count for replaced cells
//convert arr to A	-- 1 <-- G , Integer.MAX_VALUE/2 <-- #
for(int i=0; i<m; i++){
for(int j=0; j<n; j++){
if(arr[i][j]=='G'){
A[i][j]=1;
tcount++;
}
else if(arr[i][j]=='#'){
A[i][j]= Integer.MAX_VALUE/2;
tcount++;
}
}
}

f1(A, tcount);

//convert A to buff	-- 1 --> G , Integer.MAX_VALUE/2 --> #, any no. i --> i-1
for(int i=0; i<m; i++){
for(int j=0; j<n; j++){
if(A[i][j]==1){
buff[i][j]='G';

}
else if(A[i][j]==Integer.MAX_VALUE/2){
buff[i][j]= '#';

}
else{
int val=A[i][j];
buff[i][j]= Character.forDigit(val-1, 10);
}
}
}
return buff;
}

private static void f1(int[][] A, int tcount){
int m= A.length;
int n= A[0].length;
int minVal=1;
while(tcount<m*n){
int temp=minVal;
for(int i=0; i<m; i++){
for(int j=0; j<n; j++){
if(A[i][j]==minVal){

if(i>0 && A[i][j]==minVal && A[i-1][j]==0){
A[i-1][j]=minVal+1;
temp=minVal+1;
tcount++;
}
if(i<m-1 && A[i][j]==minVal && A[i+1][j]==0){
A[i+1][j]=minVal+1;
temp=minVal+1;
tcount++;
}
if(j<n-1 && A[i][j]==minVal && A[i][j+1]==0){
A[i][j+1]=minVal+1;
temp=minVal+1;
tcount++;
}
if(j>0 && A[i][j]==minVal && A[i][j-1]==0){
A[i][j-1]=minVal+1;
temp=minVal+1;
tcount++;
}

}
}

}
//System.out.println(tcount);
minVal= Math.max(temp, minVal);
}
}
}``````

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

Basically doing BFS from each guard and updating only if the distance is better than the distance at that cell (no need for a hash table)

``````package guards;

public class guards {
public static final int G = 0;
public static final int \$ = -1;
public static final int _ = Integer.MAX_VALUE;

public static void fillSpaces(int[][] mat) {
for(int i=0;i<mat.length;i++) {
for(int k=0;k<mat[0].length;k++) {
if(mat[i][k]==G) {
}
}
}

while(!v.isEmpty()) {
Tuple2 node = v.remove();
}
}

private static LinkedList<Tuple2> getNeighbors(Tuple2 node, int[][] mat) {
int i=node.A;
int k=node.B,dist = mat[i][k]+1;
int[] y = {i-1,i+1,i,i};
int[] x = {k,k,k-1,k+1};

for(int m=0;m<x.length;m++) {
if(x[m]>=0&&y[m]>=0&&x[m]<mat[0].length&&y[m]<mat.length) {
if(mat[y[m]][x[m]]>0&&mat[y[m]][x[m]]>dist) {
mat[y[m]][x[m]] = dist;
}
}
}

}

public static void main(String[] args) {
int[][] floor = {
{_,\$,_,G,_},
{_,_,\$,_,_},
{G,_,_,_,_},
{_,_,\$,_,_}
};

fillSpaces(floor);

for(int i=0;i<floor.length;i++) {
for(int k=0;k<floor[0].length;k++) {
if(floor[i][k] == G) {
System.out.print("G,");
} else if(floor[i][k] == \$) {
System.out.print("#,");
} else {
System.out.print(floor[i][k]+",");
}
}
System.out.print("\n");
}
}

}``````

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

Simple solution. Once you understand the logic, you can apply to many other problems by
doing some minor changes. (e.g. Maze, Knights Movement, N-Queen, Sudoku etc.)

``````import java.util.Arrays;

public class MuseumGuardian {
static int[] moveX = {0,  0, 1, -1};
static int[] moveY = {1, -1, 0, 0};

public static void main(String[] args) {
char[][] board =
{
{'.', '#', '.', 'G', 'G'},
{'.', '.', '#', '.', '.'},
{'G', '.', '.', '.', '.'},
{'.', '.', '#', '.', '.'}

};

solve(board);
for (char[] arr : board) {
System.out.println(Arrays.toString(arr));
}
}

/// Helper Methods
static int atoi(char c) {
return c - '0';
}

static char itoa(int n) {
return (char)('0' + n);

}

public static void solve(char[][] A) {
for (int i = 0; i < A.length; i++) {
for (int j = 0; j < A[0].length; j++) {
if (A[i][j] == 'G') {
markNeighbors(A, i, j, 0);
}
}
}
}

public static boolean isSafe(char[][] A, int i, int j, int newValue) {
if (i < 0 || i >= A.length || j < 0 || j >= A[0].length) {
return false;
}

if (A[i][j] == 'G' || A[i][j] == '#') {
return false;
}

if (A[i][j] != '.' && atoi(A[i][j]) <= newValue) {
return false;
}

return true;
}

public static void markNeighbors(char[][] A, int i, int j, int value) {
for (int k = 0; k < moveX.length; k++) {
int nextX = i + moveX[k];
int nextY = j + moveY[k];

if (isSafe(A, nextX, nextY, value + 1)) {
A[nextX][nextY] = itoa(value + 1);
markNeighbors(A, nextX, nextY, value + 1);
}
}
}
}``````

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

Can someone explain the question in a better way?

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

This will do it (a graph solution). The idea is to present each element of array as Node with information of its children. Each node will have a computed "cost" this is simply a minimum distance from Node to Guard.

import java.util.ArrayList;
import java.util.List;

/**
* @author Yura Tkachenko
*/
public class Node {
private int cost;
private boolean computedCost;
private boolean guard;
private boolean obstacle;
private boolean lock;
private int maxThreshold;
private List<Node> children = new ArrayList<Node>();

public Node(String initializer) {
if ("#".equalsIgnoreCase(initializer)) {
setObstacle(true);
} else if ("G".equalsIgnoreCase(initializer)) {
setGuard(true);
}
}

public int getMaxThreshold() {
return maxThreshold;
}

public void setMaxThreshold(int maxThreshold) {
this.maxThreshold = maxThreshold;
}

}

public boolean isLock() {
return lock;
}

public void setLock(boolean lock) {
this.lock = lock;
}

public int getCost() {
return cost;
}

public void setCost(int cost) {
this.cost = cost;
}

public boolean isComputedCost() {
return computedCost;
}

public void setComputedCost(boolean computedCost) {
this.computedCost = computedCost;
}

public boolean isGuard() {
return guard;
}

public void setGuard(boolean guard) {
this.guard = guard;
}

public boolean isObstacle() {
return obstacle;
}

public void setObstacle(boolean obstacle) {
this.obstacle = obstacle;
}

public void computeCost() {
int k = getMaxThreshold();
if (isComputedCost() || isLock()) {
return;
}
setLock(true);
// find if any children is G or has cost of 1
for (Node child : children) {
if (child.isGuard()) {
k = 1;
break;
}
if (child.isObstacle() || child.isLock()) {
continue;
}
if (!child.isComputedCost()) {
child.computeCost();
}
if (child.isComputedCost()) {
k = Math.min(k, child.getCost()+1);
}
}
setCost(k);
setComputedCost(true);
setLock(false);
}

public void balanceCost() {
for (Node child : children) {
if (!isGuard() || !isObstacle()) {
child.setCost(Math.min(getCost() + 1, child.getCost()));
}
}
}

@Override
public String toString() {
if (isGuard()) {
return "G";
} else if (isObstacle()) {
return "#";
} else if (!isComputedCost()){
return ".";
} else {
return String.valueOf(getCost());
}
}
}

List<Node> nodes = new ArrayList<Node>();
for (int i=0; i<input.length; i++) {
for (int j=0; j<input[i].length; j++) {
}
}
// set children
for (int i=0; i<input.length; i++) {
for (int j=0; j<input[i].length; j++) {
int currentIndex = i*input[0].length+j;
int leftIndex = currentIndex-1;
int rightIndex = currentIndex+1;
int topIndex = currentIndex - input[0].length;
int bottomIndex = currentIndex + input[0].length;
Node currentNode = nodes.get(currentIndex);
currentNode.setMaxThreshold(nodes.size());
if (leftIndex >= i*input[0].length) {
}
if (rightIndex < (i+1)*input[0].length) {
}
if (topIndex >= 0) {
}
if (bottomIndex < nodes.size()) {
}
}
}
return nodes.toArray(new Node[nodes.size()]);
}

public static void main(String[] args) {
String[][] arr = new String[][] {
{".","#",".","G","."},
{".",".","#",".","."},
{"G",".",".",".","."},
{".",".","#",".","."}
};
int i = 1;
String line = "";
for (Node node : nodes) {
node.computeCost();
}
for (Node node : nodes) {
node.balanceCost();
line += node.toString();
if (i % 5 == 0) {
System.out.println(line);
line = "";
}
i++;
}
System.out.println("End");
}
}

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

``````import java.util.ArrayList;
import java.util.List;

/**
* @author Yura Tkachenko
*/
public class Node {
private int cost;
private boolean computedCost;
private boolean guard;
private boolean obstacle;
private boolean lock;
private int maxThreshold;
private List<Node> children = new ArrayList<Node>();

public Node(String initializer) {
if ("#".equalsIgnoreCase(initializer)) {
setObstacle(true);
} else if ("G".equalsIgnoreCase(initializer)) {
setGuard(true);
}
}

public int getMaxThreshold() {
return maxThreshold;
}

public void setMaxThreshold(int maxThreshold) {
this.maxThreshold = maxThreshold;
}

}

public boolean isLock() {
return lock;
}

public void setLock(boolean lock) {
this.lock = lock;
}

public int getCost() {
return cost;
}

public void setCost(int cost) {
this.cost = cost;
}

public boolean isComputedCost() {
return computedCost;
}

public void setComputedCost(boolean computedCost) {
this.computedCost = computedCost;
}

public boolean isGuard() {
return guard;
}

public void setGuard(boolean guard) {
this.guard = guard;
}

public boolean isObstacle() {
return obstacle;
}

public void setObstacle(boolean obstacle) {
this.obstacle = obstacle;
}

public void computeCost() {
int k = getMaxThreshold();
if (isComputedCost() || isLock()) {
return;
}
setLock(true);
// find if any children is G or has cost of 1
for (Node child : children) {
if (child.isGuard()) {
k = 1;
break;
}
if (child.isObstacle() || child.isLock()) {
continue;
}
if (!child.isComputedCost()) {
child.computeCost();
}
if (child.isComputedCost()) {
k = Math.min(k, child.getCost()+1);
}
}
setCost(k);
setComputedCost(true);
setLock(false);
//            balanceCost();
}

public void balanceCost() {
for (Node child : children) {
if (!isGuard() || !isObstacle()) {
child.setCost(Math.min(getCost() + 1, child.getCost()));
}
}
}

@Override
public String toString() {
if (isGuard()) {
return "G";
} else if (isObstacle()) {
return "#";
} else if (!isComputedCost()){
return ".";
} else {
return String.valueOf(getCost());
}
}
}

List<Node> nodes = new ArrayList<Node>();
for (int i=0; i<input.length; i++) {
for (int j=0; j<input[i].length; j++) {
}
}
// set children
for (int i=0; i<input.length; i++) {
for (int j=0; j<input[i].length; j++) {
int currentIndex = i*input[0].length+j;
int leftIndex = currentIndex-1;
int rightIndex = currentIndex+1;
int topIndex = currentIndex - input[0].length;
int bottomIndex = currentIndex + input[0].length;
Node currentNode = nodes.get(currentIndex);
currentNode.setMaxThreshold(nodes.size());
if (leftIndex >= i*input[0].length) {
}
if (rightIndex < (i+1)*input[0].length) {
}
if (topIndex >= 0) {
}
if (bottomIndex < nodes.size()) {
}
}
}
return nodes.toArray(new Node[nodes.size()]);
}

public static void main(String[] args) {
String[][] arr = new String[][] {
{".","#",".","G","."},
{".",".","#",".","."},
{"G",".",".",".","."},
{".",".","#",".","."}
};
int i = 1;
String line = "";
for (Node node : nodes) {
node.computeCost();
}
for (Node node : nodes) {
node.balanceCost();
line += node.toString();
if (i % 5 == 0) {
System.out.println(line);
line = "";
}
i++;
}
System.out.println("End");
}
}``````

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

dijstra

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.

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

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