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];

		Queue<Position> q = new LinkedList<Position>();
		// 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;
	}
}

- sandeep1001 May 23, 2016 | Flag Reply
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");
    }
}

- chase June 10, 2016 | Flag Reply
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--;
			}
		}
	}			
}

- guilhebl May 18, 2016 | Flag Reply
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)

- Anonymous May 18, 2016 | Flag Reply
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)

- PandaSloth May 18, 2016 | Flag Reply
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

- EPavlova May 20, 2016 | Flag Reply
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;
}

- tanmay001 May 20, 2016 | Flag Reply
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];
	
	Queue<Position> q = new LinkedList<Position>();
// 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;	
}
}

- Sandeep May 23, 2016 | Flag Reply
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>();
		queue.add(new Element(x, y));
		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;
				traveledPaths.add(parent);
				ArrayList<Element> children = getAdjacentChildren(traveledPaths, parent);
				queue.addAll(children);
				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;
		}
	}
	
	protected ArrayList<Element> getAdjacentChildren(ArrayList<Element> traveledPaths,
			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();
	}

}

- jcgarciarojas May 27, 2016 | Flag Reply
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)

- Daniel Muñoz June 01, 2016 | Flag Reply
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)

    updates = 0
    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
                        updates += 1
                if x < (size-1):
                    res = test_cell(museum[x+1][y], museum[x][y])
                    if res:
                        museum[x][y] = res
                        updates += 1
                if y > 0:
                    res = test_cell(museum[x][y-1], museum[x][y])
                    if res:
                        museum[x][y] = res
                        updates += 1
                if y < (size-1):
                    res = test_cell(museum[x][y+1], museum[x][y])
                    if res:
                        museum[x][y] = res
                        updates += 1

    if updates > 0:
        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)

- Slava June 07, 2016 | Flag Reply
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");
    }
}

- C June 10, 2016 | Flag Reply
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);
    }
}

- peter tang June 16, 2016 | Flag Reply
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)
                visited.add((x, y))
                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()

- diogo.neves June 17, 2016 | Flag Reply
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))

- doorholder June 30, 2016 | Flag Reply
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) {
	// your code goes here
	
	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;
}

- Anonymous July 27, 2016 | Flag Reply
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) {
	// your code goes here
	
	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;
}

- Varun July 27, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Can you explain the problem with an example please?

- Asif July 29, 2016 | Flag Reply
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)

- Anonymous August 23, 2016 | Flag Reply
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;
    }

- cheeyim September 29, 2016 | Flag Reply
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’){
				squares.add(new Square(i, j, 0));
				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;
			}
		}
	}




}

- libertythecoder October 25, 2016 | Flag Reply
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)) {
                    guardPosList.add(new Position(x, y));
                }
            }
        }

        // 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
            // adjusted.
            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;
        }
    }
}

- boyw165 December 06, 2016 | Flag Reply
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) {
			// System.out.println("already done: "+node);
			return;
		}
		r[node.x][node.y] = node.distance+1;
	}

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

		Queue<Node> queue = new LinkedList<Node>();

		// 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
					queue.add(new Node(i,j,-1));
				}
				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);
			
			// calc adjacent verticies
			// DOWN
			int distance = node.distance + 1;
			if(node.x+1 < r.length && r[node.x+1][node.y] == -1)
				queue.add(new Node(node.x+1, node.y, distance));
			// DOWN LEFT
			if(node.x+1 < r.length && node.y-1 >= 0 && r[node.x+1][node.y-1] == -1)
				queue.add(new Node(node.x+1,node.y-1, distance));
			// DOWN RIGHT
			if(node.x+1 < r.length && node.y+1 < r[0].length && r[node.x+1][node.y+1] == -1)
				queue.add(new Node(node.x+1, node.y+1, distance));
			// UP
			if((node.x-1) >= 0 && r[node.x-1][node.y] == -1)
				queue.add(new Node(node.x-1, node.y, distance));
			// UP LEFT
			if(node.x-1 >= 0 && node.y-1 >= 0 && r[node.x-1][node.y-1] == -1)
				queue.add(new Node(node.x-1,node.y-1, distance));
			// UP RIGHT
			if(node.x-1 >= 0 && node.y+1 < r[0].length && r[node.x-1][node.y+1] == -1)
				queue.add(new Node(node.x-1, node.y+1, distance));
			// LEFT
			if((node.y-1) >= 0 && r[node.x][node.y-1] == -1)
				queue.add(new Node(node.x, node.y-1, distance));
			// RIGHT
			if((node.y+1) < r[0].length && r[node.x][node.y+1] == -1)
				queue.add(new Node(node.x, node.y+1, distance));
		}

		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("");
	}
}

- ZeroCool January 14, 2017 | Flag Reply
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]

- krupen.ghetiya July 26, 2017 | Flag Reply


Add a Comment
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.

Learn More

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.

Learn More

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.

Learn More

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.

Learn More