Facebook 2015暑期实习面经

刚刚才面试的Facebook的题目，感觉我没有见过。
w是wall，然后g是gates，从“_”开始，找出所有到gates的距离。 我折腾了半天没有做出来，面试官还是挺耐心的，全当是积累经验了。
// _ W G _
// _ _ _ W
// _ W _ W
// G W _ _

String [][] maze = new int [width][height];
boolean [][] wasHere = new boolean[width][height];

public void solution(int ma

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

   return min(left, right, up, down);
}


这是输出的结果：
// 3 W G 1
// 2 2 1 W
// 1 W 2 W
// G W 3 4



补充内容 (2015-4-8 03:46):
上面的代码是基本的思路，我没有做出来，最后没时间了。

是找出_到最近的gate的距离吗？
我记得在地里看到过类似的题，思路是BFS, 但先把所有gates的位置放在queue里面
这是那个类似的题目 http://www.1point3acres.com/bbs/thread-127776-1-1.html
地里的资料看来的好好学习啊

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维数组自动被转成了一维。。擦。。

时间空间复杂度都是O(m*n), 每个点遍历一次即可

1. //Assume '_' is 0, 'G' is 1, 'W' is 2
   
2.         private class Position{
   
3.                 int x;
   
4.                 int y;
   
5.                 public Position(int x, int y){
   
6.                         this.x = x;
   
7.                         this.y = y;
   
8.                 }
   
9.         }
   
10.         public void findLen(int[][] matrix){
    
11.                 int m = matrix.length;
    
12.                 if(m<1) return;
    
13.                 int n = matrix[0].length;
    
14.                 int[][] result = new int[m][n];
    
15.                 boolean[][] visited = new boolean[m][n];
    
16.                 Queue<Position> queue = new LinkedList<Position>();
    
17.                 int curLevel_nums = 0;
    
18.                 int nextLevel_nums = 0;
    
19.                 int level = 1;
    
20.                 for(int i=0; i<m; ++i){
    
21.                         for(int j=0; j<n; ++j){
    
22.                                 if(matrix[i][j] == 1){//enqueue gate
    
23.                                         visited[i][j] = true;
    
24.                                         queue.add(new Position(i, j));
    
25.                                         curLevel_nums++;
    
26.                                 }
    
27.                         }
    
28.                 }
    
29.                 while(!queue.isEmpty()){
    
30.                         Position cur = queue.poll();
    
31.                         curLevel_nums--;
    
32.                         int[] arr = {1,-1,1,-1};
    
33.                         for(int i=0; i<arr.length; ++i){
    
34.                                 Position newP;
    
35.                                 if(i<2){
    
36.                                         newP = new Position(cur.x+arr[i], cur.y);
    
37.                                 }
    
38.                                 else{
    
39.                                         newP = new Position(cur.x, cur.y+arr[i]);
    
40.                                 }
    
41.                                 if(newP.x<0 || newP.x>=m || newP.y<0 || newP.y>=n || visited[newP.x][newP.y]){
    
42.                                         continue;
    
43.                                 }
    
44.                                 else{
    
45.                                         if(matrix[newP.x][newP.y]==2){
    
46.                                                 visited[newP.x][newP.y] = true;
    
47.                                                 result[newP.x][newP.y] = -1;
    
48.                                         }
    
49.                                         else{//matrix[newP.x][newP.y]==0
    
50.                                                 visited[newP.x][newP.y] = true;
    
51.                                                 result[newP.x][newP.y] = level;
    
52.                                                 queue.add(newP);
    
53.                                                 nextLevel_nums++;
    
54.                                         }
    
55.                                 }
    
56.                         }
    
57.                         if(curLevel_nums==0){
    
58.                                 curLevel_nums = nextLevel_nums;
    
59.                                 nextLevel_nums = 0;
    
60.                                 level++;
    
61.                         }
    
62.                 }
    
63.                
    
64.                 //print
    
65.                 for(int i=0; i<m; ++i){
    
66.                         for(int j=0; j<n; ++j){
    
67.                                 System.out.print(result[i][j]+ "  ");
    
68.                         }
    
69.                         System.out.println();
    
70.                 }
    
71.         }

复制代码

这题不简单啊...lz啥时候投的intern啊？过了多久让面试的啊？

flyPacific111 发表于 2015-4-8 03:41
这题不简单啊...lz啥时候投的intern啊？过了多久让面试的啊？

我是3月下旬投的，面试过了2周左右吧。

实习这么难的题目额

pat pat，以后还有机会啦！
这题G经常考，可以用同步从所有的G开始做DFS

补充内容 (2015-4-8 05:26):
*BFS, not DFS，具体代码在下面的帖子里，请轻拍 =)

seabiscuit119 发表于 2015-4-8 03:49
实习这么难的题目额

没办法，实习就是这样。这可能跟Team有关，面试我的是一个team leader，难不难看这个team要什么样的人。

marthew777 发表于 2015-4-8 03:53
pat pat，以后还有机会啦！
这题G经常考，可以用同步从所有的G开始做DFS

大神能把代码贴出来吗，谢谢。

不是很理解题意。。。是说所有W到所有G的距离？有很多Gate的话，算哪个距离

shawlin 发表于 2015-4-8 03:57
是找出_到最近的gate的距离吗？
我记得在地里看到过类似的题，思路是BFS, 但先把所有gates的位置放在queue ...

嗯，有点类似。