Google Interview Question for Software Engineers


Country: United States
Interview Type: Phone Interview




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

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

using namespace std;

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

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

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

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

void bfs(const Vertex& v)
{
    bool visited[X][Y] = { false };
    queue<Vertex> q;
    
    q.push(v);
    visited[v.x][v.y] = true;
    
    int len = 0;
    int levelCount = q.size();
    
    while (q.size())
    {
        Vertex v = q.front();
        q.pop();
        
        if (len < LEN[v.x][v.y])
            LEN[v.x][v.y] = len;
        
        vector<Vertex> a = getAdjacent(v);
        for (unsigned i = 0; i != a.size(); ++i)
        {
            if (!visited[a[i].x][a[i].y]) 
            {
                q.push(Vertex(a[i].x, a[i].y));
                visited[a[i].x][a[i].y] = true;
            }
        }
        
        --levelCount;
        
        if (levelCount == 0)
        {
            ++len;
            levelCount = q.size();
        }
    }
}


int main()
{
    // Run BFS from each GUARD
    for (int i = 0; i != X; ++i)
        for (int j = 0; j != Y; ++j)
            if (M[i][j] == 'G')
                bfs(Vertex(i, j));
    
    // Print the result
    for (int i = 0; i != X; ++i)
    {
        for (int j = 0; j != Y; ++j)
        {
            if (M[i][j] != 'G' && M[i][j] != '#')
                cout << LEN[i][j];
            else 
                cout << M[i][j];
        }
        cout << endl;
    }
                
}

- Sergey May 06, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

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

- Anonymous July 03, 2015 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

import java.util.Arrays;

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

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

                };

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

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

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

    }

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

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

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

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

        return true;
    }

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

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

- Onur AktaƟ June 06, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

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

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

                };

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

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

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

    }

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

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

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

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

        return true;
    }

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

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

- Onur Aktas June 06, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- SK May 05, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- guilhebl May 05, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

exactly.

- SK May 05, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- chaithanya May 06, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static void main(String[] args){
		String[][] input = new String[4][5];
		input[0][0] = ".";
		input[0][1] = "#";
		input[0][2] = ".";
		input[0][3] = "G";
		input[0][4] = ".";
		
		input[1][0] = ".";
		input[1][1] = ".";
		input[1][2] = "#";
		input[1][3] = ".";
		input[1][4] = ".";
		
		input[2][0] = "G";
		input[2][1] = ".";
		input[2][2] = ".";
		input[2][3] = ".";
		input[2][4] = ".";
		
		input[3][0] = ".";
		input[3][1] = ".";
		input[3][2] = "#";
		input[3][3] = ".";
		input[3][4] = ".";
		
		printInput(input);
		getDistanceMatrix(input);
		printInput(input);
	}
	
	static void printInput(String[][] input){
		for(int row = 0; row < input.length; row++){
			for(int col = 0; col < input[0].length; col++){
				System.out.print(input[row][col]);
				if(col == input[0].length-1){
					System.out.print("\n");
				}
			}
		}
	}
	
	static void getDistanceMatrix(String[][] input){
		for(int row = 0; row < input.length; row++){
			for(int col = 0; col < input[0].length; col++){
				if(input[row][col].equals(".")){
					input[row][col] = getDistance(input, row, col);
				}
			}
		}
	}
	
	static String getDistance(String[][] input, int row, int col){
		int MAX = Integer.MAX_VALUE;
		int rowDistance = MAX; 
		int r = row; 
		//previous row
		while(r > 0){
			r--;
			if(input[r][col].equals("G")){
				rowDistance = 1;
				break;
			}
			try{
				rowDistance = Integer.parseInt(input[r][col])+1;
				break;
			}catch(Exception e){
				
			}
		}
		
		int guardIdx = -1; 
		int obstacleNum = 0; 
		// next row
		for(r = row+1; r < input.length; r++){
			if(input[r][col].equals("G")){
				guardIdx = r; 
				break;
			}
			if(input[r][col].equals("#")){
				obstacleNum++;
			}
		}
		if(guardIdx > 0){
			rowDistance = Math.min(rowDistance, guardIdx-row-obstacleNum);
		}
		
		int colDistance = MAX; 
		int c = col; 
		//previous col
		while(c > 0){
			c--;
			if(input[row][c].equals("G")){
				rowDistance = 1;
				break;
			}
			try{
				colDistance = Integer.parseInt(input[row][c])+1;
				break;
			}catch(Exception e){
				
			}
		}
		
		guardIdx = -1; 
		obstacleNum = 0; 
		//next Col
		for(c = col+1; c < input[0].length; c++){
			if(input[row][c].equals("G")){
				guardIdx = c; 
				break;
			}
			if(input[row][c].equals("#")){
				obstacleNum++; 
			}
		}
		
		if(guardIdx > 0){
			colDistance = Math.min(colDistance, guardIdx-col-obstacleNum);
		}
		
		int distance = Math.min(rowDistance, colDistance);
		return String.valueOf(distance);

}

- vic May 05, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Joe May 05, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@Joe
Thanks for letting me know the error.

I fixed the error.

public static void main(String[] args){
	//test data
	String[][] input = {{".", "#", ".", "G", "."}, 
						{".", ".", "#", ".", "."},
						{".", "G", ".", ".", "."},
						{".", ".", "#", ".", "."}};
	
	// print the initial matrix
	printInput(input);
	// get distance matrix
	getDistanceMatrix(input);
	// print the distance matrix
	printInput(input);
}

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

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

/**
 * set the distance value of each position
 * 
 * @param input
 * @param row
 * @param col
 * @param distance
 * @param cache
 */
static void setDistance(String[][] input, int row, int col, int distance, HashMap<String, Integer> cache){
	if(row < 0 || col < 0 || row >= input.length || col >= input[0].length || input[row][col].equals("#")){
		return;
	}
	
	String key = row+","+col;
	if(cache.containsKey(key) && distance >= cache.get(key)){
		return;
	}
	
	if(input[row][col].equals(".") || (!input[row][col].equals("#") && !input[row][col].equals("G"))){ // number
		distance = getMinDistance(input, row, col, distance);
		input[row][col] = String.valueOf(distance);
		cache.put(key, Integer.parseInt(input[row][col]));
	}else{
		cache.put(key, 0);
	}
	if(!input[row][col].equals("#")){ 
		distance++;
	}
	
	setDistance(input, row, col-1, distance, cache);
	setDistance(input, row-1, col, distance, cache);
	setDistance(input, row, col+1, distance, cache);
	setDistance(input, row+1, col, distance, cache);
}

/**
 * Find minimum distance from top, bottom, left and right
 * 
 * @param input
 * @param row
 * @param col
 * @param distance
 * @return
 */
static int getMinDistance(String[][] input, int row, int col, int distance){
	int MAX = Integer.MAX_VALUE;
	int top = MAX; 
	int bottom = MAX; 
	int left = MAX; 
	int right = MAX; 
	
	//get top value of G
	if(row > 0){
		int r = row-1; 
		while(r >= 0){
			if(input[r][col].equals("G")){
				top = 1; 
				break;
			}else if(input[r][col].equals("#")){
				r--;
			}else if(input[r][col].equals(".")){
				break;
			}else{
				top = Integer.parseInt(input[r][col])+1;
				break;
			}
		}
		
		if(distance > top){
			distance = top; 
		}
	}
	
	// get bottom value of G
	if(row < input.length){
		int r = row+1; 
		while(r <= input.length-1){
			if(input[r][col].equals("G")){
				bottom = 1; 
				break;
			}else if(input[r][col].equals("#")){
				r++;
			}else if(input[r][col].equals(".")){
				break;
			}else{
				bottom = Integer.parseInt(input[r][col])+1;
				break;
			}
		}
		
		if(distance > bottom){
			distance = bottom; 
		}
	}
	
	// get left value of G
	if(col > 0){
		int c = col-1; 
		while(c >= 0){
			if(input[row][c].equals("G")){
				left = 1; 
				break;
			}else if(input[row][c].equals("#")){
				c--;
			}else if(input[row][c].equals(".")){
				break;
			}else{
				left = Integer.parseInt(input[row][c])+1;
				break;
			}
		}
		if(distance > left){
			distance = left; 
		}
	}
	
	// get right value of G
	if(col < input[0].length){
		int c = col+1; 
		while(c <= input[0].length-1){
			if(input[row][c].equals("G")){
				right = 1; 
				break;
			}else if(input[row][c].equals("#")){
				c++;
			}else if(input[row][c].equals(".")){
				break;
			}else{
				right = Integer.parseInt(input[row][c])+1;
				break;
			}
		}
		if(distance > right){
			distance = right; 
		}
	}
	return distance;
}

- vic May 11, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@Joe
Thanks.
I fixed the error.

I use recursive method from guard position.

public static void main(String[] args){
	//test data
	String[][] input = {{".", "#", ".", "G", "."}, 
						{".", ".", "#", ".", "."},
						{".", "G", ".", ".", "."},
						{".", ".", "#", ".", "."}};
	
	// print the initial matrix
	printInput(input);
	// get distance matrix
	getDistanceMatrix(input);
	// print the distance matrix
	printInput(input);
}

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

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

/**
 * set the distance value of each position
 * 
 * @param input
 * @param row
 * @param col
 * @param distance
 * @param cache
 */
static void setDistance(String[][] input, int row, int col, int distance, HashMap<String, Integer> cache){
	if(row < 0 || col < 0 || row >= input.length || col >= input[0].length || input[row][col].equals("#")){
		return;
	}
	
	String key = row+","+col;
	if(cache.containsKey(key) && distance >= cache.get(key)){
		return;
	}
	
	if(input[row][col].equals(".") || (!input[row][col].equals("#") && !input[row][col].equals("G"))){ // number
		distance = getMinDistance(input, row, col, distance);
		input[row][col] = String.valueOf(distance);
		cache.put(key, Integer.parseInt(input[row][col]));
	}else{
		cache.put(key, 0);
	}
	if(!input[row][col].equals("#")){ 
		distance++;
	}
	
	setDistance(input, row, col-1, distance, cache);
	setDistance(input, row-1, col, distance, cache);
	setDistance(input, row, col+1, distance, cache);
	setDistance(input, row+1, col, distance, cache);
}

/**
 * Find minimum distance from top, bottom, left and right
 * 
 * @param input
 * @param row
 * @param col
 * @param distance
 * @return
 */
static int getMinDistance(String[][] input, int row, int col, int distance){
	int MAX = Integer.MAX_VALUE;
	int top = MAX; 
	int bottom = MAX; 
	int left = MAX; 
	int right = MAX; 
	
	//get top value of G
	if(row > 0){
		int r = row-1; 
		while(r >= 0){
			if(input[r][col].equals("G")){
				top = 1; 
				break;
			}else if(input[r][col].equals("#")){
				r--;
			}else if(input[r][col].equals(".")){
				break;
			}else{
				top = Integer.parseInt(input[r][col])+1;
				break;
			}
		}
		
		if(distance > top){
			distance = top; 
		}
	}
	
	// get bottom value of G
	if(row < input.length){
		int r = row+1; 
		while(r <= input.length-1){
			if(input[r][col].equals("G")){
				bottom = 1; 
				break;
			}else if(input[r][col].equals("#")){
				r++;
			}else if(input[r][col].equals(".")){
				break;
			}else{
				bottom = Integer.parseInt(input[r][col])+1;
				break;
			}
		}
		
		if(distance > bottom){
			distance = bottom; 
		}
	}
	
	// get left value of G
	if(col > 0){
		int c = col-1; 
		while(c >= 0){
			if(input[row][c].equals("G")){
				left = 1; 
				break;
			}else if(input[row][c].equals("#")){
				c--;
			}else if(input[row][c].equals(".")){
				break;
			}else{
				left = Integer.parseInt(input[row][c])+1;
				break;
			}
		}
		if(distance > left){
			distance = left; 
		}
	}
	
	// get right value of G
	if(col < input[0].length){
		int c = col+1; 
		while(c <= input[0].length-1){
			if(input[row][c].equals("G")){
				right = 1; 
				break;
			}else if(input[row][c].equals("#")){
				c++;
			}else if(input[row][c].equals(".")){
				break;
			}else{
				right = Integer.parseInt(input[row][c])+1;
				break;
			}
		}
		if(distance > right){
			distance = right; 
		}
	}
	return distance;
}

- vic May 11, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- Anonymous May 05, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

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


MAX = 10000000


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

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

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


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

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

- Brad May 05, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

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


MAX = 10000000


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

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

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


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

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

- brad May 05, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

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


MAX = 10000000


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

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

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


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

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

- brad May 05, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

dynamic programming anyone ? wake up people

- gen-x-s May 06, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

// Simple BFS

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

using namespace std;

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

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

struct Vertex
{
int x;
int y;

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

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

return a;
}

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

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

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

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

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

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

--levelCount;

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


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

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

}

- Sergey May 06, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

// Simple BFS

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

using namespace std;

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

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

struct Vertex
{
int x;
int y;

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

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

return a;
}

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

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

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

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

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

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

--levelCount;

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


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

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

}

- Sergey May 06, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

using namespace std;

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

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

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

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

void bfs(const Vertex& v)
{
    bool visited[X][Y] = { false };
    queue<Vertex> q;
    
    q.push(v);
    visited[v.x][v.y] = true;
    
    int len = 0;
    int levelCount = q.size();
    
    while (q.size())
    {
        Vertex v = q.front();
        q.pop();
        
        if (len < LEN[v.x][v.y])
            LEN[v.x][v.y] = len;
        
        vector<Vertex> a = getAdjacent(v);
        for (unsigned i = 0; i != a.size(); ++i)
        {
            if (!visited[a[i].x][a[i].y]) 
            {
                q.push(Vertex(a[i].x, a[i].y));
                visited[a[i].x][a[i].y] = true;
            }
        }
        
        --levelCount;
        
        if (levelCount == 0)
        {
            ++len;
            levelCount = q.size();
        }
    }
}


int main()
{
    // Run BFS from each GUARD
    for (int i = 0; i != X; ++i)
        for (int j = 0; j != Y; ++j)
            if (M[i][j] == 'G')
                bfs(Vertex(i, j));
    
    // Print the result
    for (int i = 0; i != X; ++i)
    {
        for (int j = 0; j != Y; ++j)
        {
            if (M[i][j] != 'G' && M[i][j] != '#')
                cout << LEN[i][j];
            else 
                cout << M[i][j];
        }
        cout << endl;
    }
                
}

- Sergey May 06, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

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

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

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

void bfs(const Vertex& v)
{
    bool visited[X][Y] = { false };
    queue<Vertex> q;
    
    q.push(v);
    visited[v.x][v.y] = true;
    
    int len = 0;
    int levelCount = q.size();
    
    while (q.size())
    {
        Vertex v = q.front();
        q.pop();
        
        if (len < LEN[v.x][v.y])
            LEN[v.x][v.y] = len;
        
        vector<Vertex> a = getAdjacent(v);
        for (unsigned i = 0; i != a.size(); ++i)
        {
            if (!visited[a[i].x][a[i].y]) 
            {
                q.push(Vertex(a[i].x, a[i].y));
                visited[a[i].x][a[i].y] = true;
            }
        }
        
        --levelCount;
        
        if (levelCount == 0)
        {
            ++len;
            levelCount = q.size();
        }
    }
}


int main()
{
    // Run BFS from each GUARD
    for (int i = 0; i != X; ++i)
        for (int j = 0; j != Y; ++j)
            if (M[i][j] == 'G')
                bfs(Vertex(i, j));
    
    // Print the result
    for (int i = 0; i != X; ++i)
    {
        for (int j = 0; j != Y; ++j)
        {
            if (M[i][j] != 'G' && M[i][j] != '#')
                cout << LEN[i][j];
            else 
                cout << M[i][j];
        }
        cout << endl;
    }
}

- Sergey May 07, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

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

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

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

void bfs(const Vertex& v)
{
    bool visited[X][Y] = { false };
    queue<Vertex> q;
    
    q.push(v);
    visited[v.x][v.y] = true;
    
    int len = 0;
    int levelCount = q.size();
    
    while (q.size())
    {
        Vertex v = q.front();
        q.pop();
        
        if (len < LEN[v.x][v.y])
            LEN[v.x][v.y] = len;
        
        vector<Vertex> a = getAdjacent(v);
        for (unsigned i = 0; i != a.size(); ++i)
        {
            if (!visited[a[i].x][a[i].y]) 
            {
                q.push(Vertex(a[i].x, a[i].y));
                visited[a[i].x][a[i].y] = true;
            }
        }
        
        --levelCount;
        
        if (levelCount == 0)
        {
            ++len;
            levelCount = q.size();
        }
    }
}


int main()
{
    // Run BFS from each GUARD
    for (int i = 0; i != X; ++i)
        for (int j = 0; j != Y; ++j)
            if (M[i][j] == 'G')
                bfs(Vertex(i, j));
    
    // Print the result
    for (int i = 0; i != X; ++i)
    {
        for (int j = 0; j != Y; ++j)
        {
            if (M[i][j] != 'G' && M[i][j] != '#')
                cout << LEN[i][j];
            else 
                cout << M[i][j];
        }
        cout << endl;
    }
}

- Sergey May 07, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

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

public class MazeScanner {
	public static char[][] space = {
		{'.', '#', '.', 'G', '.' },
		{'.', '.', '#', '.', '.' },
		{'G', '.', '.', '.', '.' },
		{'.', '.', '#', '.', '.' },
	};
	
	static class Position {
		int x;
		int y;
		
		Position(int x, int y) {
			this.x = x;
			this.y = y;
		}
		
		@Override
		public boolean equals(Object obj) {
			if (!(obj instanceof Position)) {
				return false;
			}
			
			Position pos = (Position) obj;
			
			if (this.x == pos.x && this.y == pos.y) {
				return true;
			}
			
			return false;
 		}
		
		@Override
		public String toString() {
			return "(" + x + ", " + y + ")";
		}
	}
	
	public static Integer[][] solveMaze(char[][] space, Position guard) {		
		Integer[][] output = new Integer[space.length][space[0].length];
		List<Position> visited = new ArrayList<>();

		for (int i = 0; i < output.length; ++i) {
			for (int j = 0; j < output[0].length; ++j) {
				output[i][j] = -1;
			}
		}
		
		Queue<Position> queue = new LinkedList<>();
		
		output[guard.x][guard.y] = 0;
		queue.add(guard);
		
		while (! queue.isEmpty()) {
			Position position = queue.poll();
			
			if (output[position.x][position.y] == -1) {
				Integer value = getNearestValue(output, position.x, position.y);
			    
			    output[position.x][position.y] = value + 1;
			}
			
			List<Position> positions = getPossibleNeighours(space, position, visited);
			
			if (positions.size() >= 1) {
				queue.addAll(positions);
				visited.addAll(positions);
			}
		}
		
		
		return output;
	}
	
	public static String[][] solveMaze(char[][] space, Position[] guards) {
		Integer[][] output = new Integer[space.length][space[0].length];
		List<Integer[][]> possibleSolutions = new ArrayList<>();
		
		for (int i = 0; i < guards.length; ++i) {
			Integer[][] out = solveMaze(space, guards[i]);
			
			//print2DArray(out);
			
			possibleSolutions.add(out);
		}
		
		for (int i = 0; i < output.length; ++i) {
			for (int j = 0; j < output[0].length; ++j) {
				int minimumPositive = Integer.MAX_VALUE;
				
				for (int z = 0; z < possibleSolutions.size(); ++z) {
					if (possibleSolutions.get(z)[i][j] < minimumPositive && possibleSolutions.get(z)[i][j] > 0) {
						minimumPositive = possibleSolutions.get(z)[i][j];
					}
				}
				
				if (minimumPositive != Integer.MAX_VALUE) {
					output[i][j] = minimumPositive;
				} else {
					output[i][j] = -1;
				}
			}
		}
		
		String[][] finalOutput = new String[space.length][space[0].length];
		
		for (int i = 0; i < finalOutput.length; ++i) {
			for (int j = 0; j < finalOutput[0].length; ++j) {
				if (output[i][j] > 0 && space[i][j] != 'G' && space[i][j] != '#') {
					finalOutput[i][j] = output[i][j] + "";
				} else {
					finalOutput[i][j] = space[i][j] + "";
				}
			}
		}
		
		return finalOutput;		
	}
 	
	
	private static Integer getNearestValue(Integer[][] output, Integer x, Integer y) {
		if (x + 1 <= output.length - 1 && output[x + 1][y] != -1) {
			return output[x + 1][y];
		}
		
		if (x - 1 >= 0 && output[x - 1][y] != -1) {
			return output[x - 1][y];
		}

		if (y + 1 <= output[0].length - 1 && output[x][y + 1] != -1) {
			return output[x][y + 1];
		}
		
		if (y - 1 >= 0 && output[x][y - 1] != -1) {
			return output[x][y - 1];
		}		
		
		throw new RuntimeException("[Severe] cannot get a nearest value ...");
	}


	private static List<Position> getPossibleNeighours(char[][] space, Position position, List<Position> visited) {
		int x = position.x; 
		int y = position.y;
		
		List<Position> positions = new ArrayList<>();
		
		if (x + 1 <= space.length - 1 && space[x + 1][y] != '#' && space[x + 1][y] != 'G') {
			Position pos = new Position(x + 1, y);
			
			if (! visited.contains(pos)) {
			    positions.add(pos);
			}
		}
		
		if (x - 1 >= 0 && space[x - 1][y] != -1 && space[x - 1][y] != '#' && space[x - 1][y] != 'G') {
			Position pos = new Position(x - 1, y);
			
			if (! visited.contains(pos)) {
				positions.add(pos);
			}
		}

		if (y + 1 <= space[0].length - 1 && space[x][y + 1] != -1 && space[x][y + 1] != '#' && space[x][y + 1] != 'G') {
			Position pos = new Position(x, y + 1);
			
			if (! visited.contains(pos)) {
				positions.add(pos);
			}
		}
		
		if (y - 1 >= 0 && space[x][y - 1] != -1 && space[x][y - 1] != '#' && space[x][y - 1] != 'G') {
			Position pos = new Position(x, y - 1);			
			
			if (! visited.contains(pos)) {
				positions.add(pos);
			}
		}
		
		return positions;
	}


	public static void main(String[] args) {
		Position[] positions = new Position[] {
				new Position(2, 0),
				new Position(0, 3)
		};
		
		String[][] output = solveMaze(space, positions);
		
		print2DArray(output);
	}
	
	public static<T> void print2DArray (T[][] output) {
		for (int i = 0; i < output.length; ++i) {
			for (int j = 0; j < output[0].length; ++j) {
				System.out.print(output[i][j] + "  ");
			}
			System.out.println("  ");
		}
	}
	
}

- Good Maker May 07, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

Please reply if you find any ambiguity in the algorithm.

- madhur.eng May 09, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- amirtar May 09, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- amirtar May 09, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- madhur.eng May 09, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

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

class Pairs {

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

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

    public int getRow() {
        return row;
    }

    public int getCol() {
        return col;
    }

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

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

}

class Museum {

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

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

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

    public Map<Pairs, Integer> getGuardDistance() {

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

//Create output format
        return distances;
    }

}

- amirtar May 09, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

package arrays;

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

public class GuardEmptySpace {

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

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

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

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

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

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

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

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

    private void changeQueue(String str, int i, int j) {
        StringBuilder sb = new StringBuilder(str);
        if (isGoodCell(i, j)) {
            q.add(sb.append(";").append(i).append(",").append(j).toString());
            set.add(i + "," + j);
        }
    }

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

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

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

- madhur.eng May 09, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- amirtar May 09, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

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

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

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

- Nilesh Agrawal May 10, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

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

- JW May 13, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

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

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

- zortlord May 20, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public class HelloWorld{

     public static void main(String []args){
        char input[][]= {{'.','#','.','G','.'}, {'.','.','#','.','.'}, {'G','.','.','.','.'}, {'.','.','#','.','.'}} ;
        
        char[][] result= f(input);
        for(int i=0; i<result.length; i++){
            for(int j=0; j<result[0].length; j++){
                System.out.print(result[i][j]+" ");
            }
            System.out.println();
        }
     }
     
     public static char[][] f(char[][] arr){
	int m= arr.length;
	int n= arr[0].length;
	char[][] buff= new char[m][n];
	int[][] A= new int[m][n];
	int tcount=0; // count for replaced cells
	//convert arr to A	-- 1 <-- G , Integer.MAX_VALUE/2 <-- #
	for(int i=0; i<m; i++){
		for(int j=0; j<n; j++){
			if(arr[i][j]=='G'){
				A[i][j]=1;
				tcount++;
			}
			else if(arr[i][j]=='#'){
				A[i][j]= Integer.MAX_VALUE/2;
				tcount++;
			}
		}
	}
	
	f1(A, tcount);

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

private static void f1(int[][] A, int tcount){
    int m= A.length;
	int n= A[0].length;
	int minVal=1;
	while(tcount<m*n){
	    int temp=minVal;
		for(int i=0; i<m; i++){
			for(int j=0; j<n; j++){
				if(A[i][j]==minVal){
					
					if(i>0 && A[i][j]==minVal && A[i-1][j]==0){
						A[i-1][j]=minVal+1;
						temp=minVal+1;
						tcount++;
					}
					if(i<m-1 && A[i][j]==minVal && A[i+1][j]==0){
						A[i+1][j]=minVal+1;
						temp=minVal+1;
						tcount++;
					}
					 if(j<n-1 && A[i][j]==minVal && A[i][j+1]==0){
						A[i][j+1]=minVal+1;
						temp=minVal+1;
						tcount++;
					}
					 if(j>0 && A[i][j]==minVal && A[i][j-1]==0){
						A[i][j-1]=minVal+1;
						temp=minVal+1;
						tcount++;
					}
					
				}
			}
		
		}
		//System.out.println(tcount);
		minVal= Math.max(temp, minVal);
	}
}
}

- infinity May 24, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

package guards;

import java.util.LinkedList;

public class guards {
	public static final int G = 0;
	public static final int $ = -1;
	public static final int _ = Integer.MAX_VALUE;
	
	public static void fillSpaces(int[][] mat) {
		LinkedList<Tuple2> v = new LinkedList<Tuple2>();
		for(int i=0;i<mat.length;i++) {
			for(int k=0;k<mat[0].length;k++) {
				if(mat[i][k]==G) {
					v.add(new Tuple2(i,k));
				}
			}
		}
		
		while(!v.isEmpty()) {
			Tuple2 node = v.remove();
			v.addAll(getNeighbors(node,mat));
		}
	}

	private static LinkedList<Tuple2> getNeighbors(Tuple2 node, int[][] mat) {
		int i=node.A;
		int k=node.B,dist = mat[i][k]+1;
		int[] y = {i-1,i+1,i,i};
		int[] x = {k,k,k-1,k+1};
		LinkedList<Tuple2> adj = new LinkedList<Tuple2>();
		
		for(int m=0;m<x.length;m++) {
			if(x[m]>=0&&y[m]>=0&&x[m]<mat[0].length&&y[m]<mat.length) {
				if(mat[y[m]][x[m]]>0&&mat[y[m]][x[m]]>dist) {
					mat[y[m]][x[m]] = dist;
					adj.add(new Tuple2(y[m],x[m]));
				}
			}
		}
		
		return adj;
	}
	
	public static void main(String[] args) {
		int[][] floor = {
				{_,$,_,G,_},
				{_,_,$,_,_},
				{G,_,_,_,_},
				{_,_,$,_,_}
		};
		
		fillSpaces(floor);
		
		for(int i=0;i<floor.length;i++) {
			for(int k=0;k<floor[0].length;k++) {
				if(floor[i][k] == G) {
					System.out.print("G,");
				} else if(floor[i][k] == $) {
					System.out.print("#,");
				} else {
					System.out.print(floor[i][k]+",");
				}
			}
			System.out.print("\n");
		}
	}
	
}

- Franklyn May 29, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

import java.util.Arrays;

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

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

                };

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

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

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

    }

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

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

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

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

        return true;
    }

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

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

- onurraktas June 06, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Can someone explain the question in a better way?

- Tejas June 30, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

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

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

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

public int getMaxThreshold() {
return maxThreshold;
}

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

public void addChild(Node n) {
children.add(n);
}

public boolean isLock() {
return lock;
}

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

public int getCost() {
return cost;
}

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

public boolean isComputedCost() {
return computedCost;
}

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

public boolean isGuard() {
return guard;
}

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

public boolean isObstacle() {
return obstacle;
}

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

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

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

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

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


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

- Yuri T. July 06, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

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

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

        public int getMaxThreshold() {
            return maxThreshold;
        }

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

        public void addChild(Node n) {
            children.add(n);
        }

        public boolean isLock() {
            return lock;
        }

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

        public int getCost() {
            return cost;
        }

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

        public boolean isComputedCost() {
            return computedCost;
        }

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

        public boolean isGuard() {
            return guard;
        }

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

        public boolean isObstacle() {
            return obstacle;
        }

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

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

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

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

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


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

- Yuri T. July 06, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

dijstra

- sakar2003 December 28, 2015 | 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