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
地里的资料看来的好好学习啊

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

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

时间空间复杂度都是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 ...

嗯，有点类似。