Facebook 2015暑期实习面经

yuxrose 发表于 2015-4-8 04:03
不是很理解题意。。。是说所有W到所有G的距离？有很多Gate的话，算哪个距离

是“_”到G的距离。每一个“_”到G的距离，W是不能经过的，有一点像迷宫。

JermaineDing 发表于 2015-4-8 03:56
大神能把代码贴出来吗，谢谢。

大概是这个意思，其实很简单达！

private enum BLOCK {G, W, O};
public void solution(int[][] maze){
        int m = maze.length;
        if(m<1) return;
        int n = maze[0].length;
        boolean[][] visited = new boolean[m][n];
        Arrays.fill(visited, false);
        int[][] sol = new int[m][n];
        Arrays.fill(sol, 0);
        Queue<Queue<Position>> queue = new LinkedList<>();
        for(int i=0;i<m;++i)
                for(int j=0;j<n;++j)
                        if(maze[i][j]==G){
                                queue.add(new LinkedList<>(){new Position(i,j)});
                                sol[i][j] = 1;
                                visited[i][j] = true;
                        }
        while(!queue.isEmpty()){
                Queue<Position> bfs = queue.poll();
                Position p = bfs.poll();
                // bfs : up
                if(isValid(maze, i, j-1, visited)){
                        bfs.add(new Position(i, j-1));
                        sol[i][j-1] = sol[i][j] + 1;
                        visited[i][j-1]=true;
                }
                // similarly do: left down and right
                if(isValid(maze, i, j+1, visited)){
                        //...
                }
                if(isValid(maze, i-1, j, visited)){
                        //...                       
                }
                if(isValid(maze, i+1, j, visited)){
                        //...               
                }
        }
}
public boolean isValid(int[][] maze, int i, int j, boolean[][] visited){
        int m = maze.length;
        if(m<1)
                return false;
        int n = maze[0].length;
        if(i<0 || i >= m || j < 0 || j >= n || visited[i][j] || maze[i][j]==W)
                return false;
        return true;
}
public class Position{
        public int x;
        public int y;
        public Position(int x, int y){
                this.x = x; this.y = y;
        }
}

补充内容 (2015-4-8 04:32):
最后的结果就保存在 int[][] sol里，如果知道W的值的话，也可以再做一次简单的iteration把相应的W的值更新到sol里。。

marthew777 发表于 2015-4-8 04:29
大概是这个意思，其实很简单达！

private enum BLOCK {G, W, O};

请问dfs为什么不行?我用dfs实现了，方便的话帮我看下

1. public List<Integer> pathToGates(char[][] maze) {
   
2.                 ArrayList<Integer> res = new ArrayList<Integer>();
   
3.                 if (maze.length == 0 && maze[0].length == 0) {
   
4.                         return res;
   
5.                 }
   
6.                 int[][] visit = new int[maze.length][maze[0].length];
   
7.                 for (int i = 0; i < maze.length; i++) {
   
8.                         for (int j = 0; j < maze[0].length; j++) {
   
9.                                 help(maze, i, j, res, 0 , visit);
   
10.                         }
    
11.                        
    
12.                 }
    
13.                
    
14.                 return res;
    
15.         }
    
16.        
    
17.         public void        help(char[][] maze , int i , int j , ArrayList<Integer> res, int count, int[][] visit) {
    
18.                 if (i < 0 || i >= maze.length || j < 0 || j >= maze[0].length ||visit[i][j] == 1 || maze[i][j] == 'W') {
    
19.                        
    
20.                         return;
    
21.                 }else if (maze[i][j] == 'G') {
    
22.                         res.add(count);
    
23.                        
    
24.                         return;
    
25.                 }
    
26.                 visit[i][j] = 1;
    
27.                 count++;
    
28.                 help(maze, i+1, j, res, count,visit);
    
29.                 help(maze, i-1, j, res, count,visit);
    
30.                 help(maze, i, j+1, res, count,visit);
    
31.                 help(maze, i, j-1, res, count,visit);
    
32.                 visit[i][j] = 0;
    
33.                 count--;
    
34.         }
    
35.        
    
36.         public static void main(String[] args) {
    
37.                
    
38.                
    
39.                 rotate rr = new rotate();
    
40.                 char[][] maze = new char[4][4];
    
41.                 maze[0][0] = '_';
    
42.                 maze[0][1] = 'W';
    
43.                 maze[0][2] = 'G';
    
44.                 maze[0][3] = '_';
    
45.                 maze[1][0] = '_';
    
46.                 maze[1][1] = '_';
    
47.                 maze[1][2] = '_';
    
48.                 maze[1][3] = 'W';
    
49.                 maze[2][0] = '_';
    
50.                 maze[2][1] = 'W';
    
51.                 maze[2][2] = '_';
    
52.                 maze[2][3] = 'W';
    
53.                 maze[3][0] = 'G';
    
54.                 maze[3][1] = 'W';
    
55.                 maze[3][2] = '_';
    
56.                 maze[3][3] = '_';
    
57.                
    
58.                 System.err.println(rr.pathToGates(maze));
    
59.                
    
60.                
    
61.         }

复制代码

haungge0385 发表于 2015-4-8 21:15
请问dfs为什么不行?我用dfs实现了，方便的话帮我看下

要求是找到最短的距离，显然是BFS啊。。

楼主和我的题目一模一样。。

chm34 发表于 2015-4-8 22:24
楼主和我的题目一模一样。。

是什么时候面的？是Facebook吗？

JermaineDing 发表于 2015-4-9 01:52
是什么时候面的？是Facebook吗？

恩，礼拜一面的，我之前在地里也没见过这题，然后我用dfs写的，但是应该是有bug，后来没时间了，昨天收到rej

marthew777 发表于 2015-4-8 04:29
大概是这个意思，其实很简单达！

private enum BLOCK {G, W, O};

哥，你这代码有问题呀，略坑...

siren01 发表于 2015-4-9 05:30
哥，你这代码有问题呀，略坑...

补充内容 (2015-4-9 07:20):
测试用的是 每次随机生成5x5 maze，Gate 和 Wall 都是在随机的位置； 总共进行了10次测试；
每次测试的输出，第一行是输入的maze: -1 代表Wall, 1代表Gate; 第二行是输出的solution；

siren01 发表于 2015-4-9 05:30
哥，你这代码有问题呀，略坑...

上面的代码我说了是给一个算法实现的大概思路，肯定有syntax error的好吗，我花几分钟随手写的。。
完整代码我分享出来给大家好了！测试过的，没问题，您看看这次还有问题么


import java.util.*;
class Solution{
public static int[][] solution(int[][] maze){
        int m = maze.length;
        if(m<1) return new int[m][m];
        int n = maze[0].length;
        boolean[][] visited = new boolean[m][n];
        for(boolean[] row : visited)
                Arrays.fill(row, false);
        int[][] sol = new int[m][n];
        for(int[] row : sol)
                Arrays.fill(row, 0);
        Queue<Queue<Position>> queue = new LinkedList<>();
        for(int i=0;i<m;++i)
                for(int j=0;j<n;++j)
                        if(maze[i][j]==1){
                                Queue<Position> gate = new LinkedList<>();
                                gate.add(new Position(i,j));
                                queue.add(gate);
                                sol[i][j] = 0;
                                visited[i][j] = true;
                        }
        while(!queue.isEmpty()){
                Queue<Position> bfs = queue.poll();
                Position p = bfs.poll();
                int i = p.x, j = p.y;
                // bfs : up
                if(isValid(maze, i, j-1, visited)){
                        bfs.add(new Position(i, j-1));
                        sol[i][j-1] = sol[i][j] + 1;
                        visited[i][j-1]=true;
                }
                // similarly do: left down and right
                if(isValid(maze, i, j+1, visited)){
                        bfs.add(new Position(i, j+1));
                        sol[i][j+1] = sol[i][j] + 1;
                        visited[i][j+1]=true;
                }
                if(isValid(maze, i-1, j, visited)){
                        bfs.add(new Position(i-1, j));
                        sol[i-1][j] = sol[i][j] + 1;
                        visited[i-1][j]=true;           
                }
                if(isValid(maze, i+1, j, visited)){
                        bfs.add(new Position(i+1, j));
                        sol[i+1][j] = sol[i][j] + 1;
                        visited[i+1][j]=true;   
                }
                if(!bfs.isEmpty())
                        queue.add(bfs);
        }
        return sol;
}
public static boolean isValid(int[][] maze, int i, int j, boolean[][] visited){
        int m = maze.length;
        if(m<1)
                return false;
        int n = maze[0].length;
        if(i<0 || i >= m || j < 0 || j >= n || visited[i][j] || maze[i][j]==-1)
                return false;
        return true;
}
public static class Position{
        public int x;
        public int y;
        public Position(int x, int y){
                this.x = x; this.y = y;
        }
}
public static void printMaze(int[][] maze){
        System.out.println(Arrays.deepToString(maze));
}
public static void main(String[] args){
        // For simplicity, assuming W(-1), O(0), G(1)
        Random rdm = new Random();
        int size = 5;
        int[][] test = new int[size][size];
        // Generate Random Gates and initilize rest cells on maze
        for(int i=0;i<size;i++)
                for(int j=0;j<size;j++)
                        test[i][j]=rdm.nextInt(2);
        // Generate Random Walls      
        int num_walls = 2;
        for(int i=0;i<num_walls;++i){
                int x = rdm.nextInt(size);
                int y = rdm.nextInt(size);
                test[x][y] = -1;
        }
        printMaze(test);
        printMaze(solution(test));
}
}


补充内容 (2015-4-9 07:43):
以前没有发过代码到帖子里，发现2维数组自动被转成了一维。。擦。。