## Google Interview Question for Software Engineer / Developers

Country: United States
Interview Type: In-Person

Comment hidden because of low score. Click to expand.
11
of 15 vote

Typed it in directly... so expect bugs (or plain incorrectness :P )
BFS initiated from all guard positions and +1 for reaching a naked position (a '0') and add it to queue to keep the BFS search going.

``````//Assuming N x N matrix and directions are up/down/left/right

#define IN_BOUNDARY(a,b) ((a)>=0 && (a)<N && (b)>=0 && (b)<N)

typedef struct { int x, y; } Pos;  //struct for a "position" of a node (indices)

//find and enqueue guard positions
queue <Pos> Q;
Pos temp;
int i, j;
for (i=0; i < N; i++)
for(j=0; j < N; j++)
if( A[i][j] == 'G' ) {
temp.x=i;
temp.y=j;
Q.push(temp); //putting guard position in Q
}

//BFS
while(!Q.empty()) {

temp=Q.front(); Q.pop();
i=temp.x;
j=temp.y;

for( int u=-1; u < 2; u++)
for( int v=-1; v < 2; v++)
if( (!u||!v) && IN_BOUNDARY(i+u, j+v) && A[i+u][j+v]=='0')
{
//should reach here for only/all valid naked neighbours
A[i+u][j+v]=A[i][j]+1;  //distance to neighbour is 1 more

temp.x=i+u;
temp.y=j+v;
Q.push(temp);  //push neighbour onto queue
}
}``````

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

Lol treat G as 1 inside while loop

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

So, the queue keeps both position of G, and naked position '0'?

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

^^^ Yes, because all growing shortest paths start at a G and go through a '0' (they do not revisit a numbered node again).

My "Lol" comment above was referring to this fix:

``A[i+u][j+v]=A[i][j]+1;``

should be

``A[i+u][j+v]= (A[i][j]=='G')? 1: A[i][j]+1;``

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

Got it! Thanks.

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

Can this algorith ensure that the distance is from the nearest Guard point, I think we have to write like this :

``````if(A[i + u][j + v] == 0 || A[i+u][j+v] > A[i][j] +１)
Ａ［i+u］[j+v] = A[i][j] + 1``````

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

I think the algorithm didn't handle the nearest gaurd points case. Your algorithm might return the longest routes to all the 0 from a given set of gaurds. What if the gaurd point you are starting is not the right candidate for a '0' zero node. There is a possibility that this '0' node can be reached from another gaurd point which is much close.

So we need to correct the logic to take the min( existing a[i][j] and new a[i][j])

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

This solution doesn't check if the cell is a obstacle and can not be crossed.

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

Distance to A[i-1][j-1] or A[i+1][j+1] is at least distance to A[i][j] +2.
Directly we can calculate only distance to A[i-1][j] , A[i+1][j], A[i][j-1] , and A[i][j+1].

Comment hidden because of low score. Click to expand.
3
of 5 vote

Below is my code, I did some test.
-2 for block, -1 for gurad.

``````void dfs(vector<vector<int>>& matrix, int x, int y, int step){
if (x < 0 || y < 0 || x >= matrix.size() || y >= matrix[0].size()) return;
if (matrix[x][y] < 0) return;
if (matrix[x][y]>step + 1 || matrix[x][y] == 0)
matrix[x][y] = step + 1;
else return;
dfs(matrix, x + 1, y, step + 1);
dfs(matrix, x, y + 1, step + 1);
dfs(matrix, x - 1, y, step + 1);
dfs(matrix, x, y - 1, step + 1);
}

void RoomGuard(vector<vector<int>>&matrix){
for (int i = 0; i < matrix.size(); i++){
for (int j = 0; j < matrix[0].size(); j++){
if (matrix[i][j] == -1){
dfs(matrix, i-1, j, 0);
dfs(matrix, i, j-1, 0);
dfs(matrix, i +1, j, 0);
dfs(matrix, i , j+1, 0);
}
}
}
}``````

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

DFS goes deep as far as it can in one direction, before trying others.

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

@AngryAlgorist, that's true. But is there anything wrong with my code?

Comment hidden because of low score. Click to expand.
-2

I am not sure :(
How can you guarantee that "step" is always the shortest path reachable from that guard? Can you explain it?

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

Well, you can think this as some kind of paint-fill algorithm.

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

Paint fill is boolean filling of nodes...so dfs vs.bfs has same effect because u are just visiting all suitable nodes.

This is shortest distance filling... So dfs usually does not work.

Comment hidden because of low score. Click to expand.
-2

Well, you can write some test cases to see if this works,LOL

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

@Mem, took a closer look, and I see what you are doing here. You are repeatedly trying all paths, even if they reuse the same spots, so long as going through the spot is cheaper than any previous path through that spot.

Cool idea!

The idea should work but it worst case complexity should be large.

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

BFS from every guard. However: once you reach node whose distance from guard you do not improve, ignore it. If the matrix has N cells and G guards the complexity is O(NG);

``````import java.util.LinkedList;
import java.util.List;

import util.Utils;

public class MinDistanceFromGuards {

private static int G = -1;
private static int B = -2;

public static void setDistances(int [][] mat){
int nCols = mat[0].length;
int nRows = mat.length;
for(int i = 0; i < nRows; i ++){
for(int j = 0; j < nCols; j++){
}
}

while(!guards.isEmpty()){
while(!nodes.isEmpty()){
Node cur = nodes.removeFirst(); // cur already processed
int r = cur.row, c = cur.col;

int matVal = mat[r][c];
int dist = cur.dist;

if(matVal >= 0) {
if(matVal == 0 || dist < matVal) mat[r][c] = dist;
else continue;
}

dist++;
// above
if(r > 0) addNode(nodes,mat,r-1, c, dist);
// below
if(r+1 < nRows) addNode(nodes,mat,r+1, c, dist);
//left
//right

}

}

}

private static void addNode(List<Node> nodes, int [][]mat,  int r, int c, int val){
}

private static class Node {
int row;
int col;
int dist;

Node(int r, int c, int val){
row = r;
col = c;
dist = val;
}
}

public static void main(String[] args) {
int [][] mat = {
{ 0, 0, 0 },
{B, G, G},
{B, 0, 0}
};
test(mat);

int [][] mat2 = {
{0, 0, B, 0, 0 },
{B, G, 0, G, 0},
{0, 0, B, B, 0},
{0, 0, 0, 0, 0}
};
test(mat2);

}

private static void test(int[][] mat) {
System.out.println("Input:");
System.out.println(Utils.matrixToString(mat));
setDistances(mat);

System.out.println("Output:");
System.out.println(Utils.matrixToString(mat));
System.out.println("----------------------");
}

}``````

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

bfs...

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

Yes, bfs. But interviewer said there is an optimal solution with O(n^2), which I haven't figured out. :(

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

I think we can use bfs twice to solve this problem, from node (0,0) to (n,n), then reverse from (n,n) to (0,0)

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

bfs...
initiate the queue with all "G" cells.

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

Could there be anything possibly wrong with using BFS and putting G nodes into the priority queue?

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

Here's another approach, Find the coordinate of the G nodes. For each node, find the Manhattan distance between the Coordinates and the G nodes, assign the value as the smallest manhattan distance. This takes O(n^3) though. The BFS technique with all G nodes in the Priority queue should be the fastest (as someone else suggested)

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

``````#include <iostream>

int array[][3] = {{0,0,0},{-2,-1,-1},{-2,0,0}};

template <typename T>
T min(T a, T b)
{
if (a < b) return a;
return b;
}

void print()
{
for (int i = 0; i < 3; ++i)
{
for (int j = 0; j < 3; ++j)
{
std::cout << array[i][j] << ",";
}
std::cout << "\n";
}
}

void markhere(int i, int j, int mark)
{
if (array[i][j] > 0)
{
array[i][j] = min(array[i][j], mark);
}
else if (array[i][j] == 0)
{
array[i][j] = mark;
}
}

void mark()
{
bool done = false;
int current =  -1;
int mark = 1;
while (!done)
{
done = true;
for (int i = 0; i < 3; ++i)
{
for (int j  = 0 ; j < 3; ++j)
{
if (array[i][j] == current)
{
if (j > 0)
{
done = false;
markhere(i, j - 1, mark);
}
if (j < 2)
{
done = false;
markhere(i, j + 1, mark);
}
if (i < 2)
{
done = false;
markhere(i + 1, j, mark);
}
if (i > 0)
{
done = false;
markhere(i - 1, j, mark);
}
}
}
}
current = mark;
mark++;
}
}

int main()
{
print();
mark();
print();
return 0;
}``````

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

time o(n) space o(n), get all the guard nodes to a min-heap and expand them to adjacent nodes, keep adding them to the min-heap if reachable. assuming obstacle is -2, guard is -1 for easy processing.

``````struct Node {
int x;
int y;
int distance;

Node(int x_i, int y_i, int distance_i) {
x = x_i;
y = y_i;
distance = distance_i;
}

bool operator>(const Node &node) const {
return distance > node.distance;
}
};

void markDistance(vector<vector<int> >& map) {
priority_queue<Node, vector<Node>, greater<Node> > min_heap;
const int x_max = map.size() - 1;
const int y_max = map[0].size() - 1;
// get the guard nodes.
for (int x = 0; x < map.size(); ++x) {
for (int y = 0; y < map[x].size(); ++y) {
if (map[x][y] == -1) {
min_heap.emplace(x, y, 0);
}
}
}
while (!min_heap.empty()) {
auto node = min_heap.top();
min_heap.pop();
for (int x = -1; x <= 1; ++x) {
for (int y = -1; y <= 1; ++y) {
// only visit the up/down/left/right node.
if ((x == 0 && y == 0) || (x != 0 && y != 0)) continue;
// get real (x, y) on the map
int x_map = node.x + x;
int y_map = node.y + y;
// skip the node out of boundary or it's obstacle and guard
if (x_map < 0 || y_map < 0 || x_map > x_max || y_map > y_max ||
map[x_map][y_map] < 0) continue;
// update the node if we have a shorter path to it or it's not visited.
if (map[x_map][y_map] == 0 || node.distance + 1 < map[x_map][y_map]) {
map[x_map][y_map] = node.distance + 1;
min_heap.emplace(x_map, y_map, map[x_map][y_map]);
}
}
}
}
}``````

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

``````/* Readable C implementation, Compiled and tested. */
#include <stdio.h>
#include <stdlib.h>
#include <limits.h>

#define Z 3

typedef struct pair {
int p;
int q;
} pair;

typedef struct queue {
int front;
int rear;
pair *a;
int n;
} queue;

queue *create_queue(int n)
{
queue *q;
q = malloc(sizeof(queue));
q->a = calloc(sizeof(*(q->a)), n);
if(!q) return q;
q->n = n;
q->front = -1;
q->rear = -1;
return q;
}

void enqueue(queue *q, pair p)
{
if((q->front + 1) % q->n == q->rear) {
printf("queue full\n");
return;
}

q->front = (q->front + 1) % q->n;
q->a[q->front] = p;

if(q->rear == -1)
q->rear = q->front;
}

int dequeue(queue *q, pair *p)
{
if(q->front == -1)
return -1;

*p = q->a[q->rear];

if(q->rear == q->front) {
q->rear = -1;
q->front = -1;
} else {
q->rear = (q->rear+1) % q->n;
}
}

void visit(int m[Z][Z], int disc[Z][Z], int dist, int p, int q, queue *qu)
{
pair p1;
if(p < 0 || p >= Z || q < 0 || q >= Z)
return;
if(m[p][q] == 'G' || m[p][q] == 'B' || dist >= m[p][q])
return;
m[p][q] = dist;
p1.p = p;
p1.q = q;
enqueue(qu, p1);
disc[p][q] = 1;
}

void bfs(int m[Z][Z], int p, int q)
{
queue *qu;
pair p1;
int disc[Z][Z] = {};
int dist;

if(m[p][q] != 'G')
return;

p1.p = p;
p1.q = q;

qu = create_queue(100);

enqueue(qu, p1);
disc[p1.p][p1.q] = 1;

while(dequeue(qu, &p1) != -1) {
if(m[p1.p][p1.q] == 'G')
dist = 1;
else
dist = m[p1.p][p1.q] + 1;

visit(m, disc, dist, p1.p-1, p1.q, qu);
visit(m, disc, dist, p1.p+1, p1.q, qu);
visit(m, disc, dist, p1.p, p1.q-1, qu);
visit(m, disc, dist, p1.p, p1.q+1, qu);

}
}

void find_dist(int m[Z][Z])
{
int i, j;

for(i = 0; i < Z; i++) {
for(j = 0; j < Z; j++) {
if(m[i][j] == 0)
m[i][j] = INT_MAX;
}
}

for(i = 0; i < Z; i++)
for(j = 0; j < Z; j++)
bfs(m, i, j);
}

int main()
{
int i, j;
int m[Z][Z] = {	{  0,   0,   0 },
{ 'B', 'G', 'G'},
{ 'B',  0,   0 }	};
find_dist(m);

for(i = 0; i < Z; i++) {
for(j = 0; j < Z; j++) {
if(m[i][j] >= 'A')
printf("%c ", (char)m[i][j]);
else
printf("%d ", m[i][j]);

}
printf("\n");
}

return 0;
}``````

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

public void setMatrix(char[][] matrix) {
for (int i=0; i<matrix.length; i++) {
for(int j=0; j<matrix[0].length; j++) {
if (matrix[i][j] != 'B' && matrix[i][j] != 'G' && matrix[i][j] != '0') continue;
matrix[i][j] = findDistanceToGuardFrom(matrix, new Point(i, j));
}
}
}

private int findDistanceToGuardFrom(int[][] matrix, Point n) {
if (isGuard(n)) {
return 0;
}
int result;
for (Point ns : getNeighbors(matrix, n)) {
result = 1 + findDistanceToGuardFrom(matrix, ns);
if (matrix[n.x][n.y] == 0 || result < matrix[n.x][n.y]) { matrix[n.x][n.y] = result; }
}
return result;
}

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

Time Complexity O( n^2 log(n) ).....
I have check for various test cases it gives perfect answer.
input matrix will be like:

``````{int[][] query1 = new int[][]{ {0,0,0},
{1,2,2},
{1,0,0}};``````

where 2 means Guard and 1 mean blocked or obstacle
distance matrix is the output matrix, in which
Max value means cant reach,
0 means, you are a guard
otherwise other numeric values.

We keep checking whether the distance of any u, u_c has changed, if yes then we re-compute the distance matrix.

``````public int[][] getMinDistanceGuardMatrix(int[][] matrix){
int[][] distance = new int[matrix.length][matrix[0].length];
distance = initializeDistanceMatrix(distance);
int maxCols = matrix[0].length;
int maxRows = matrix.length;
boolean alter = true;
while(alter){
alter = false;
for (int u = 0; u < maxRows; u++){
for(int u_c = 0; u_c < maxCols; u_c++){
if(matrix[u][u_c] == 2 & distance[u][u_c]!=0) {
distance[u][u_c] = 0;
//						System.out.println("2 " + u + "," + u_c + "= " + distance[u][u_c] );
alter = true;
}
else if(matrix[u][u_c] == 1) distance[u][u_c] = Integer.MAX_VALUE;
else if(matrix[u][u_c]==0){
//						System.out.println("0 " + u + "," + u_c + "= " + distance[u][u_c] );
int dist = Integer.MAX_VALUE;
if(u_c + 1 < maxCols && (dist > distance[u][u_c+1])){
dist = distance[u][u_c+1] + 1;
}
if(u_c - 1 > 0 && (dist > distance[u][u_c-1])){
dist = distance[u][u_c-1] + 1;
}
if(u + 1 < maxRows && (dist > distance[u+1][u_c])){
dist = distance[u+1][u_c] + 1;
System.out.println("u+1 " + u + "," + u_c + "= " + dist );
}
if(u - 1 > 0 && (dist > distance[u-1][u_c])){
dist = distance[u-1][u_c] + 1;
}
//						System.out.println(" " + u + "," + u_c + "= " + dist );
//						System.out.println(" " + u + "," + u_c + "= " + distance[u][u_c] );
if(distance[u][u_c] > dist){
distance[u][u_c] = dist;
//							System.out.println("change " + u + "," + u_c + "= " + dist );
alter = true;
}
}
}
}
//			printMatrix(distance);
}

return distance;``````

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

Find the all the guards first, populate all the surrounding empty rooms at distance 1, keep track of these rooms.
1.Find the G cells
2.Update the distance of surrounding cells found in step 1 to 1, use a list to keep track these cells been updated
3.Distance+1, repeat step 2, if the cell's distance is already there, that's definitely the shortest distance, skip this cell

public static int[][] nearestGuard(char[][] input) {
int[][] result = new int[input.length][input[0].length];
ArrayList<int[]> current = new ArrayList<int[]>();
for (int i = 0; i < input.length; i++) {
for (int j = 0; j < input[0].length; j++) {
if (input[i][j] == 'G')
current.add(new int[] { i, j });
}
}
int distance = 1;
while (!current.isEmpty()) {
ArrayList<int[]> next = new ArrayList<int[]>();
for (int[] c : current) {
guradHelper(input, c[0] + 1, c[1], distance, result, next);
guradHelper(input, c[0] - 1, c[1], distance, result, next);
guradHelper(input, c[0], c[1] + 1, distance, result, next);
guradHelper(input, c[0], c[1] - 1, distance, result, next);
}
current = next;
distance++;
}
return result;
}

public static void guradHelper(char[][] input, int i, int j, int distance,
int[][] result, ArrayList<int[]> next) {
if (i < 0 || j < 0 || i >= input.length || j >= input[0].length
|| input[i][j] == 'G' || input[i][j] == 'B'
|| result[i][j] != 0)
return;
result[i][j] = distance;
next.add(new int[] { i, j });
}

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

``````M = Given matrix
Queue dequeue = put all the G coordinates in the queue.
Queue queue = empty queue;
while(!dequeue.isEmpty())
{
Pair p = dequeue.Dequeue();
Enqueue all p's neighboring Rooms which are either '0' or less than 'p' value and increase its value by 1;
if(dequeue.isEmpty())
{
temp = queue;
queue = dequeue;
dequeue = temp;
}
}``````

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

BFS from every guard. Not very efficient as I missed the idea of putting all of the guards in the queue and only doing one run using the zeros as visited indicators. But it works :)

``````void update_from_guard(char** a, int m, int n, int gx, int gy, bool first)
{
bool** visited = new bool*[m];
for (auto i = 0; i < m; ++i) visited[i] = new bool[n];
for (auto i = 0; i < m; ++i)
for (auto j = 0; j < n; ++j) visited[i][j] = false;
std::queue<pt_t> q;
q.push(pt_t(gx, gy, 0));
visited[gx][gy] = true;
while (!q.empty())
{
pt_t p = q.front();
q.pop();
int i = std::get<0>(p);
int j = std::get<1>(p);
int d = std::get<2>(p);
if (a[i][j] >= '0' && a[i][j] <= '9')
{
if (first) a[i][j] = (char)('0' + d);
else a[i][j] = std::min(a[i][j], (char)('0' + d));
}
else if (i != gx || j != gy) continue;
if (i > 0 && !visited[i - 1][j])
{
q.push(pt_t(i - 1, j, d + 1));
visited[i - 1][j] = true;
}
if (i < m - 1 && !visited[i + 1][j])
{
q.push(pt_t(i + 1, j, d + 1));
visited[i + 1][j] = true;
}
if (j > 0 && !visited[i][j - 1])
{
q.push(pt_t(i, j - 1, d + 1));
visited[i][j - 1] = true;
}
if (j < n-1 && !visited[i][j + 1])
{
q.push(pt_t(i, j + 1, d + 1));
visited[i][j + 1] = true;
}
}
for (auto i = 0; i < m; ++i) delete[] visited[i];
delete[] visited;
}

void calc_min_guard_dist(char** a, int m, int n)
{
bool seen_guard = false;
for (auto i = 0; i < m; ++i)
for (auto j = 0; j < n; ++j)
if (a[i][j] == 'G')
{
update_from_guard(a, m, n, i, j, !seen_guard);
seen_guard = true;
}
}

void print_matrix(char** a, int m, int n)
{
for (auto i = 0; i < m; ++i)
{
for (auto j = 0; j < n; ++j)
std::cout << a[i][j] << " ";
std::cout << std::endl;
}
}

void test_calc_min_guard_dist()
{
const int m = 3, n = 3;
char** a = new char*[m];
for (auto i = 0; i < m; ++i) a[i] = new char[n];
for (auto i = 0; i < m; ++i)
for (auto j = 0; j < n; ++j)
a[i][j] = '0';
a[1][0] = 'B';
a[2][0] = 'B';
a[1][1] = 'G';
a[1][2] = 'G';
print_matrix(a, m, n);
calc_min_guard_dist(a, m, n);
print_matrix(a, m, n);
}``````

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

Initially i walk through all the nodes and store the coordinates of guards and rooms. I then calculate the absolute difference of the coordinates from room to guards to get the result.

Here is a working python code:

``````in_matrix = [[0,0,0],['B','G','G'],['B',0,0]]
room_pointers  = []
guard_pointers = []

out_matrix = in_matrix

"define a class to store the coordinates of rooms and guards"
class coordinates:
def __init__(self,x,y):
self.x = x
self.y = y

def calculate_steps():
for i in range(len(in_matrix)):
for j in range(len(in_matrix[0])):
if(in_matrix[i][j]==0):
room_pointers.append(coordinates(i,j))
elif(in_matrix[i][j]=='G'):
guard_pointers.append(coordinates(i,j))

for i in range(len(in_matrix)):
for j in range(len(in_matrix[0])):
if(in_matrix[i][j] == 0):
room = room_pointers[0]
sum = 5
for guard in guard_pointers:
temp = abs(guard.x-room.x)+abs(guard.y-room.y)
if(temp < sum): sum = temp
out_matrix[i][j] = sum
del room_pointers[0]

print("The steps from a room to nearest Guard room is: ")
print(out_matrix)

calculate_steps()``````

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

I did this question in python and basically did BFS twice. once to find where the G's are and then to spread out from the G's using a dictionary to keep track of the minimum distances dynamically.

``````def roomDist(matrix):
distDict = {}
coord = (0,0)
q = [coord]
visited = []
visitedG = []
while (q != []):
coord = q.pop(0)
i = coord[0]
j = coord[1]
element = matrix[i][j]
if (element == "G"):
visitedG.append(coord)
distDict[coord] = 1
elif (element == "B"):
distDict[coord] = float("inf")
visited.append(coord)
neighbors = getNeighbors(matrix,i,j,visited) # returns only the NON VISITED and NON OBSTACLE neighbors
for n in neighbors:
if (n not in q):
q.append(n)
newDict = roomDistHelper(matrix,visitedG,distDict)
print("\n")
for row in matrix:
t = ""
for element in row:
t += element + "\t"
print(t)

for e in newDict.keys():
i = e[0]
j = e[1]
element = matrix[i][j]
if (element == "0"):
matrix[i][j] = newDict[e]
print("Updated matrix:\n")
for row in matrix:
t = ""
for element in row:
t += str(element) + "\t"
print(t)

def roomDistHelper(matrix,visitedG,distDict):
q = visitedG
visited = []
while (q != []):
coord = q.pop(0)
i = coord[0]
j = coord[1]
element = matrix[i][j]
visited.append(coord)
neighbors = getNeighbors(matrix,i,j,visited)
for nei in neighbors:
if (nei not in q):
q.append(nei)
curValue = distDict.get(coord)
allN = allNeighbors(matrix,i,j)
for n in allN:
if (element == "G"):
distDict[n] = 1
else:
val = distDict.get(n,float("inf"))
distDict[n] = min(1 + curValue,val)
return distDict

def allNeighbors(matrix,i,j):
rList = []
right = (i+1,j) if i+1 < len(matrix) else None
down = (i,j+1) if j+1 < len(matrix[0]) else None
left = (i-1,j) if i-1 >= 0 else None
up = (i,j-1) if j-1 >= 0 else None
if(right is not None and matrix[right[0]][right[1]] != "B"):
rList.append(right)
if(left is not None and matrix[left[0]][left[1]] != "B"):
rList.append(left)
if(up is not None and matrix[up[0]][up[1]] != "B"):
rList.append(up)
if(down is not None and matrix[down[0]][down[1]] != "B"):
rList.append(down)
return rList

def getNeighbors(matrix,i,j,visited):
rList = []
right = (i+1,j) if i+1 < len(matrix) else None
down = (i,j+1) if j+1 < len(matrix[0]) else None
left = (i-1,j) if i-1 >= 0 else None
up = (i,j-1) if j-1 >= 0 else None
if(right is not None and matrix[right[0]][right[1]] != "B" and right not in visited):
rList.append(right)
if(left is not None and matrix[left[0]][left[1]] != "B"and left not in visited):
rList.append(left)
if(up is not None and matrix[up[0]][up[1]] != "B" and up not in visited):
rList.append(up)
if(down is not None and matrix[down[0]][down[1]] != "B" and down not in visited):
rList.append(down)
return rList``````

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

``````static class Coordinate {
int x, y;

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

public static void distance(char[][] matrix) {
if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
return;
}

for (int i = 0; i < matrix.length; i++) {
for (int j = 0; j < matrix[0].length; j++) {
if (matrix[i][j] == 'G') {
}
}
}

final int[][] dirs = {{0, -1}, {-1, 0}, {0, 1}, {1, 0}};

while (!q.isEmpty()) {
Coordinate curr = q.remove();

for (int[] dir : dirs) {
int x = curr.x + dir[0];
int y = curr.y + dir[1];

if (isValid(matrix, x, y) && matrix[x][y] == '0') {
matrix[x][y] = matrix[curr.x][curr.y] == 'G'
? '1'
: (char) (matrix[curr.x][curr.y] + 1);
}
}
}

for (int i = 0; i < matrix.length; i++) {
for (int j = 0; j < matrix[0].length; j++) {
if (matrix[i][j] == '0') {
matrix[i][j] = 'X';
}
}
}
}

private static boolean isValid(char[][] matrix, int x, int y) {
return x >= 0 && x < matrix.length
&& y >= 0 && y < matrix[0].length;
}``````

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

Dijkstra's algorithm should be better. And it has O(n^2) complexity.

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

Dijkstra's is not needed as this is a "every move/edge is 1 unit of weight" problem.

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

What about find shortest path from all guards? Just put them into one queue initially.

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

Could you please elaborate a bit more. Interviewer does mention to start from G, and then bfs from there. but I've run out of time by then. Thanks

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

This is what I thought, start from every G, go 4 direction, if we find current cell is B or another G we return, or if it is a number that smaller than the step we have from Current G, we also return other wise add 1 to current step and put it into current cell. Do the same recursion for current cell until no move can made. Do the same process for all G.

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

@Mem, recursion would go deep in one direction before trying others (i.e., DFS).

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

@AngryAlgorist. Yes, I admit that, but it is not possible here?

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

What I actually have meant is to run breadth first search from all guards.

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

``````public static int guards(String [][]a, int i, int j, int N, int [][]visited){
int c;

// Returns if you encounter a "B" or Index is out of bound
if (i < 0 || j < 0 || i >= N || j >= N || a[i][j] == "B")
return 0;

// If the code encounters a numeric value (minimum value) it returns (numeric value + 1). The numeric value is minimum value to reach "G"
// Using this principle you need not check the shortest distance to G for every index in the Array.
// You can simply return if you encounter B, G, Numeric value.

// Consider 	2 1 B
//			1 G B
//			0 1 G
// Array[2][0] need not check for G, its neighbor Array[1][0] or Array[2][1] (depending on the recursive call) has the minimum value of 1.
// Thus Array[2][0] minimum value is 1 + min step for Array[1][0] = 2.
// This may or may not be Array[2][0] minimum value depending on the number of recursive calls left.

if (isNumeric(a[i][j]) && Integer.parseInt(a[i][j]) > 0)
return 1+Integer.parseInt(a[i][j]);

if (a[i][j] == "G")
return 1;

if (visited[i][j]==0){

visited[i][j]=1;

// Consider the minimum value
if ((c=guards(a,i-1,j,N,visited))>0)
a[i][j]= (Integer.parseInt(a[i][j])>0?Math.min(c,Integer.parseInt(a[i][j])):c)+"";

if ((c = guards(a,i,j+1,N,visited))>0)
a[i][j]= (Integer.parseInt(a[i][j])>0?Math.min(c,Integer.parseInt(a[i][j])):c)+"";

if ((c = guards(a,i+1,j,N,visited))>0)
a[i][j]= (Integer.parseInt(a[i][j])>0?Math.min(c,Integer.parseInt(a[i][j])):c)+"";

if ((c = guards(a,i,j-1,N,visited))>0)
a[i][j]= (Integer.parseInt(a[i][j])>0?Math.min(c,Integer.parseInt(a[i][j])):c)+"";

visited[i][j]=0;

// Consider that an index's neighbor has found a G.
// Since the numeric value determined be the neighbor is the minimum, minimum value for index will be 1 + neighbor's numeric value.
return 1+Integer.parseInt(a[i][j]);

}

return 0;

}

public static boolean isNumeric(String s){

for(char c: s.toCharArray()){
if(!Character.isDigit(c))
return false;
}
return true;
}

public static void guard(String a[][]){
int N=a.length;
int visited[][]=new int[N][N];

for(int i=0;i<N;i++)
for(int j=0;j<N;j++)
visited[i][j]=0;

for(int i=0;i<N;i++)
for(int j=0;j<N;j++)
if(a[i][j] != "B" && a[i][j] != "G" && Integer.parseInt(a[i][j])==0)
guards(a,i,j,N,visited);``````

}

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

Could the person who down vote the answer care to explain ?

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

Could the person who wrote the answer, care to explain what the frack he is trying to do, first?

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

Mr. frack,

The code uses dynamic programming to find the minimum distance to the nearest guards. For example:
Consider 3 points A, B, C

Distance: B to C = 3 (shortest distance)
Distance: A to B = 2 (shortest distance)
Distance: A to C = ?

Option 1: find shortest distance from A to C by traveling from A to C
Option 2: Add shortest distance from A to B and shortest distance from B to C.

Above code uses Option 2.

Next time you down vote an answer, have a better reason than being lazy. Also please provide a test case that fails.

if you are at point A and you want to goto point C, and you re

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

I have hard coded the dimension as 3.
-1 will represent block, -2 will represent guard.

``````public class FindNearestGuard {

int[] xDiff = {0,-1, 0, 1};
int[] yDiff = {1, 0,-1, 0};

int[][] matrix = {{0,0,0},
{-1,-2,-2},
{-1,0,0}};

boolean[][] visited = new boolean[3][3];
public void findDistance()
{
int n =3;
int[][] dup = new int[3][3];
for(int i = 0 ; i < 3 ;i++)
{
for(int j = 0 ; j < 3 ; j++)
{
dup[i][j] = matrix[i][j];
}
}

for(int i = 0 ; i < 3 ; i++)
{
for(int j = 0 ; j < 3 ; j++)
{
if (matrix[i][j] == 0)
{
int res = find(i,j, 0);
dup[i][j] = res;
}
}
}

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

private int find(int x, int y, int count)
{
if (matrix[x][y] == -2)
{
return count;
}
int min = Integer.MAX_VALUE;

for(int i = 0 ; i< 4 ; i++)
{
int x1 = x + xDiff[i];
int y1 = y + yDiff[i];
if (isValid(x1, y1)&& !visited[x1][y1]&& matrix[x1][y1] != -1)
{
visited[x][y] = true;
int c = find(x1, y1, count+1);
visited[x][y] = false;
if (c < min)
{
min = c;
}
}
}

return min;
}

private boolean isValid(int x, int y)
{
return x >= 0 && x < 3 && y >= 0 && y < 3;
}
/**
* @param args
*/
public static void main(String[] args)
{
new FindNearestGuard().findDistance();

}

}``````

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

if you are posting actual compilable code , then why is your only comment "param args" ?????

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.